Table of Contents
Leetcode 1762. Buildings With an Ocean View
Problem
There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.
The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.
Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.
Example 1:
Input: heights = [4,2,3,1] Output: [0,2,3] Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.
Example 2:
Input: heights = [4,3,2,1] Output: [0,1,2,3] Explanation: All the buildings have an ocean view.
Example 3:
Input: heights = [1,3,2,4] Output: [3] Explanation: Only building 3 has an ocean view.
Constraints:
1 <= heights.length <= 1051 <= heights[i] <= 109
Source: Leetcode 1762. Buildings With an Ocean View
Solution
Approach – 1 : Right to Left
The ocean is at the right of all buildings. So, whatever the height of any other building is, the right-most building will always have the ocean view, right?
Another observation is, any building which has height smaller than the right-most building’s height will not have the ocean view! We can generalize this observation by taking the height of the right most building as maximum height so far. Then we can go towards left and update the “maximum height so far” if we find any building that is higher than current “maximum height so far”.
All buildings that make the variable “maximum height so far” updated will have the ocean view. Because, whenever we need to update “maximum height so far” for a building, this means that, that building has more height than all of the buildings on the right side of it. So, that building will have no problem to have the ocean view (no matter if any building to its left is higher than it!).
Let’s try to understand this idea with below images.
Let’s say we are given the heights array as, heights = [100, 40, 80, 70, 10, 20, 30].
Let’s have an integer max_so_far to keep the value of “maximum height so far“. Initially this is 0.
We also have an array indices[ ] (empty now) to store the indices of buildings with ocean view.
Since the right most building’s height > max_so_far, we add index 6 and update max_so_far = 30.
For the building next to the right-most one, its height (20) is less than the height of the right-most one. So, we won’t do anything for it and move to the next one.
Without further explanation, let’s observe below images one after another, it should be self explanatory and understandable. If you find it hard to understand, please write a comment in the comment section of which part was not so clear to you. We will definitely try to answer your questions!
Finally, we need to reverse the indices array since the indices will have to return in increasingly sorted order.
C++ code of Approach – 1
Below is the C++ code that implements this approach.
class Solution {
public:
vector<int> findBuildings(vector<int>& heights) {
int max_height = 0;
vector<int> indices;
for(int i = heights.size() - 1; i >= 0; i--){
if(heights[i] > max_height){
max_height = heights[i];
indices.push_back(i);
}
}
reverse(indices.begin(), indices.end());
return indices;
}
};
Approach – 2 : Left to Right – using Stack
In this approach, we will start from left and move towards right. While moving towards right, we will push the index of a building to a stack. At any point, if we find a building that is higher than the top most element of the stack, we will remove the top most element from the stack. If after removal the top most element, we still see that the current building’s height is higher than the second top most element of the stack, we will remove that as well and we will continue removing elements from stack until this condition is not true.
Why we are removing element from stack? See, if we find a building that is higher than the top most element of the stack, that means, the top most element (or building) of the stack will not have the ocean view because of the current building. So, what is the point of keeping that element in the stack, right?
Let’s examine this idea with below images. We are taking the same buildings and an empty stack of indices.
At the first step, we will simply push the index of the first building to the stack as below.
Now, moving towards right to the second element, the second buildings height is smaller than the top most building (height 100, index 0) in stack, right? (remember, we pushed the index of building, not the actual height). So, if we push index of 40 into stack, it will not block the view of 100 (or, the top-most element in stack).
Now the fun part begins when we move towards the building at index 2 (height 80). Currently, the topmost element of stack is index 1 (height 40). Now, if we push index of 80, it will block the view of 40, right? That means, we will remove 40’s index from stack and then push 80’s index. If we had multiple elements in stack, for example, 20, 30 and 40, we would have to remove all of them (because 80 will block the view of all of them) and then we would push 80’s index.
Below image shows this process.
From now on, let’s see below images for the next steps onward. These images are self explanatory. And again, if you find it hard to understand, please write a comment in the comment section of which part was not so clear to you. We will definitely try to answer your questions!
Finally, we get the stack filled with indices in the order we want. We do not need to reverse them as we did in approach – 1.
C++ code of Approach – 2
In the below C++ code, we used a vector to behave like a stack. Since the return type is a vector, we didn’t bother to use stack STL and then convert it into vector. Rather using STL vector was much simpler.
class Solution {
public:
vector<int> findBuildings(vector<int>& heights) {
int n = heights.size();
vector<int> indices;
for (int current = 0; current < n; ++current) {
// If the current building is taller,
// it will block the shorter building's ocean view to its left.
// So we pop all the shorter buildings that have been added before.
while (!indices.empty() && heights[indices.back()] <= heights[current]) {
indices.pop_back();
}
indices.push_back(current);
}
return indices;
}
};
Conclusion
Hope this post helped you understand the solution of Leetcode 1762. Buildings With an Ocean View. If you like it or hate it, please post some comments so that we can improve our writing or get motivation!
Happy Coding! 🙂