Buildings With an Ocean View — Problem & Solution
Buildings With an Ocean View solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Buildings With an Ocean View is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Stack, Monotonic Stack
- Asked at: Amazon, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n buildings in a line, and the ocean lies to the right of the last one. A building has an ocean view if every building to its right is strictly shorter.
Given the array heights, return the indices of the buildings that have an ocean view, sorted in ascending order.
Example 1
Input: heights = [4,2,3,1]
Output: [0,2,3]
Example 2
Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: Every building sees the ocean.
Example 3
Input: heights = [1,3,2,4]
Output: [3]
Constraints
1 <= heights.length <= 401 <= heights[i] <= 1000000000
Hints for Buildings With an Ocean View
Hint 1
Scan from the right, remembering the tallest building seen so far.
Hint 2
A building has a view exactly when it is strictly taller than that running maximum.
Hint 3
Collect the indices in reverse, then flip them to get ascending order.
How to solve Buildings With an Ocean View
Scan from the right keeping the tallest so far; a building has a view iff it is strictly taller than that maximum.
Approach
- For
ifrom the end, ifheights[i] > tallest, recordiand updatetallest. - Reverse the recorded indices.
Why it works
"Every building to the right is strictly shorter" is the same as "taller than the running maximum of the suffix".
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- The rightmost building always has a view.
Reference solution
Python
def findBuildings(heights):
out = []
tallest = 0
for i in range(len(heights) - 1, -1, -1):
if heights[i] > tallest:
out.append(i)
tallest = heights[i]
out.reverse()
return outJava
public static int[] findBuildings(int[] heights) {
List<Integer> collected = new ArrayList<>();
int tallest = 0;
for (int i = heights.length - 1; i >= 0; i--) {
if (heights[i] > tallest) {
collected.add(i);
tallest = heights[i];
}
}
int[] out = new int[collected.size()];
for (int i = 0; i < out.length; i++) out[i] = collected.get(out.length - 1 - i);
return out;
}C++
vector<int> findBuildings(vector<int>& heights) {
vector<int> out;
int tallest = 0;
for (int i = (int) heights.size() - 1; i >= 0; i--) {
if (heights[i] > tallest) {
out.push_back(i);
tallest = heights[i];
}
}
reverse(out.begin(), out.end());
return out;
}JavaScript
var findBuildings = function(heights) {
const out = [];
let tallest = 0;
for (let i = heights.length - 1; i >= 0; i--) {
if (heights[i] > tallest) {
out.push(i);
tallest = heights[i];
}
}
out.reverse();
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure