Solution Explanation for Buildings With an Ocean View

This problem asks us to find all buildings that have an unobstructed view of the ocean, meaning all buildings to their right are shorter. The most efficient approach involves iterating through the buildings from right to left, keeping track of the maximum height encountered so far.

Approach: Reverse Traversal and Maximum Height Tracking

1. Initialization: We start with an empty list ans to store the indices of buildings with ocean views and a variable mx initialized to 0 to track the maximum height encountered so far (from right to left).

2. Reverse Iteration: We iterate through the heights array from right to left (from the last building to the first).

3. Ocean View Check: For each building, we compare its height (heights[i]) with mx. If heights[i] > mx, it means this building is taller than all buildings to its right (because mx holds the maximum height encountered so far from the right), so it has an ocean view. We add its index i to ans and update mx to heights[i].

4. Result: After iterating through all buildings, ans will contain the indices of buildings with ocean views, but in reverse order. We reverse ans to obtain the final result sorted in increasing order.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the number of buildings. We iterate through the array once.
• Space Complexity: O(k), where k is the number of buildings with ocean views. In the worst case, k could be equal to n, so the space complexity is O(n). This space is used to store the ans array. If we disregard the space used for the output, the space complexity would be O(1).

Code Examples in Multiple Languages

The following code examples implement the described approach in several popular programming languages:

Python:

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        ans = []
        mx = 0
        for i in range(len(heights) - 1, -1, -1):
            if heights[i] > mx:
                ans.append(i)
                mx = heights[i]
        return ans[::-1]

Java:

class Solution {
    public int[] findBuildings(int[] heights) {
        List<Integer> ans = new ArrayList<>();
        int mx = 0;
        for (int i = heights.length - 1; i >= 0; --i) {
            if (heights[i] > mx) {
                ans.add(i);
                mx = heights[i];
            }
        }
        Collections.reverse(ans);
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}

C++:

class Solution {
public:
    vector<int> findBuildings(vector<int>& heights) {
        vector<int> ans;
        int mx = 0;
        for (int i = heights.size() - 1; i >= 0; --i) {
            if (heights[i] > mx) {
                ans.push_back(i);
                mx = heights[i];
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Go:

func findBuildings(heights []int) []int {
    ans := []int{}
    mx := 0
    for i := len(heights) - 1; i >= 0; i-- {
        if heights[i] > mx {
            ans = append(ans, i)
            mx = heights[i]
        }
    }
    for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
        ans[i], ans[j] = ans[j], ans[i]
    }
    return ans
}

JavaScript:

var findBuildings = function(heights) {
    let ans = [];
    let max = 0;
    for (let i = heights.length - 1; i >= 0; i--) {
        if (heights[i] > max) {
            ans.push(i);
            max = heights[i];
        }
    }
    return ans.reverse();
};

These code examples all follow the same basic algorithm, demonstrating its adaptability across different programming languages. The key is the reverse iteration and the efficient tracking of the maximum height seen so far.