Buildings With an Ocean View
Buildings With an Ocean View is a medium arrays & hashing problem solved with the right to left traversal pattern.
The best approach, optimal (right-to-left running maximum), runs in O(n) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
A row of n buildings stands along a street, and the ocean is to the right of the last one. You are given an integer array heights where heights[i] is the height of building i.
A building has an ocean view if every building to its right is strictly shorter than it. Return the indices of all buildings with an ocean view, sorted in increasing order.
Examples
Example 1
- Input
heights = [6, 2, 5, 3, 1]- Output
[0, 2, 3, 4]- Why
- Building 1 (height 2) is blocked by the 5 to its right; every other building is taller than everything after it.
Example 2
- Input
heights = [3, 3, 3]- Output
[2]- Why
- A building of equal height also blocks the view, so only the last one sees the ocean.
Example 3
- Input
heights = [1, 4, 2, 7]- Output
[3]- Why
- 7 is the tallest and sits last, so it blocks every building to its left.
Constraints
1 <= heights.length <= 10^51 <= heights[i] <= 10^9- The ocean lies to the right of the last building.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²) | O(1) |
| Monotonic stack (left to right) | O(n) | O(n) |
| Optimal (right-to-left running maximum) | O(n) | O(1) |
1Brute force
O(n²)Up to n - 1 - i comparisons for building i.O(1)Apart from the output list, only loop indices.For every building, scan all the buildings to its right and check whether any of them is at least as tall.
- For each i from 0 to n - 1:
- Check every j > i; if heights[j] >= heights[i], building i is blocked.
- If no such j exists, add i to the answer (indices come out in increasing order).
class Solution {
public int[] findBuildings(int[] heights) {
int n = heights.length;
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
boolean view = true;
for (int j = i + 1; j < n; j++) {
if (heights[j] >= heights[i]) {
view = false;
break;
}
}
if (view) res.add(i);
}
int[] out = new int[res.size()];
for (int k = 0; k < out.length; k++) out[k] = res.get(k);
return out;
}
}class Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
n = len(heights)
res = []
for i in range(n):
view = True
for j in range(i + 1, n):
if heights[j] >= heights[i]:
view = False
break
if view:
res.append(i)
return resclass Solution {
public:
vector<int> findBuildings(vector<int>& heights) {
int n = heights.size();
vector<int> res;
for (int i = 0; i < n; i++) {
bool view = true;
for (int j = i + 1; j < n; j++) {
if (heights[j] >= heights[i]) {
view = false;
break;
}
}
if (view) res.push_back(i);
}
return res;
}
};function findBuildings(heights) {
const n = heights.length;
const res = [];
for (let i = 0; i < n; i++) {
let view = true;
for (let j = i + 1; j < n; j++) {
if (heights[j] >= heights[i]) {
view = false;
break;
}
}
if (view) res.push(i);
}
return res;
}2Monotonic stack (left to right)
O(n)Each index is pushed once and popped at most once.O(n)The stack can hold all n indices (strictly decreasing input).Scan from the left and keep a stack of indices that can still see the ocean. A new building blocks every stacked building that is not taller than it, so pop those first, then push the new index. The stack stays strictly decreasing in height and, at the end, holds exactly the answer in increasing index order.
- For each i from left to right:
- While the stack is not empty and heights[top] <= heights[i], pop.
- Push i.
- Return the stack contents from bottom to top.
class Solution {
public int[] findBuildings(int[] heights) {
int[] stack = new int[heights.length];
int top = 0;
for (int i = 0; i < heights.length; i++) {
while (top > 0 && heights[stack[top - 1]] <= heights[i]) top--;
stack[top++] = i;
}
return Arrays.copyOf(stack, top);
}
}class Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
stack = []
for i, h in enumerate(heights):
while stack and heights[stack[-1]] <= h:
stack.pop()
stack.append(i)
return stackclass Solution {
public:
vector<int> findBuildings(vector<int>& heights) {
vector<int> stack;
for (int i = 0; i < (int)heights.size(); i++) {
while (!stack.empty() && heights[stack.back()] <= heights[i]) stack.pop_back();
stack.push_back(i);
}
return stack;
}
};function findBuildings(heights) {
const stack = [];
for (let i = 0; i < heights.length; i++) {
while (stack.length > 0 && heights[stack[stack.length - 1]] <= heights[i]) stack.pop();
stack.push(i);
}
return stack;
}3Optimal (right-to-left running maximum)
O(n)One pass from right to left plus a reverse of the answer.O(1)Only the running maximum besides the output.Walk from the ocean side. Keep the tallest height seen so far to the right. A building sees the ocean exactly when it is strictly taller than that maximum; then it becomes the new maximum. The indices are found in decreasing order, so reverse them at the end.
- maxRight = 0.
- For i from n - 1 down to 0: if heights[i] > maxRight, record i and set maxRight = heights[i].
- Reverse the recorded indices and return them.
class Solution {
public int[] findBuildings(int[] heights) {
List<Integer> res = new ArrayList<>();
int maxRight = 0;
for (int i = heights.length - 1; i >= 0; i--) {
if (heights[i] > maxRight) {
res.add(i);
maxRight = heights[i];
}
}
int[] out = new int[res.size()];
for (int k = 0; k < out.length; k++) out[k] = res.get(out.length - 1 - k);
return out;
}
}class Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
res = []
max_right = 0
for i in range(len(heights) - 1, -1, -1):
if heights[i] > max_right:
res.append(i)
max_right = heights[i]
res.reverse()
return resclass Solution {
public:
vector<int> findBuildings(vector<int>& heights) {
vector<int> res;
int maxRight = 0;
for (int i = (int)heights.size() - 1; i >= 0; i--) {
if (heights[i] > maxRight) {
res.push_back(i);
maxRight = heights[i];
}
}
reverse(res.begin(), res.end());
return res;
}
};function findBuildings(heights) {
const res = [];
let maxRight = 0;
for (let i = heights.length - 1; i >= 0; i--) {
if (heights[i] > maxRight) {
res.push(i);
maxRight = heights[i];
}
}
return res.reverse();
}Edge cases to test
- A single building always has the view
- Strictly decreasing heights: every building qualifies
- Strictly increasing heights: only the last building qualifies
- Equal heights: a building of the same height on the right blocks the view
Hints
Hint 1
A building sees the ocean exactly when it is strictly taller than every building to its right.
Hint 2
Instead of rescanning the right side for every building, walk from the right end and remember the tallest height seen so far.
Hint 3
Collecting from the right gives the indices in decreasing order; reverse them (or fill the result from the back) before returning.
FAQ
What is the best time complexity for Buildings With an Ocean View?
Optimal (right-to-left running maximum) runs in O(n) time and O(1) extra space. One pass from right to left plus a reverse of the answer.
Which pattern does Buildings With an Ocean View use?
It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.
Is there a brute force solution for Buildings With an Ocean View?
Yes. Brute force takes O(n²) time and O(1) space. For every building, scan all the buildings to its right and check whether any of them is at least as tall.
Which edge cases should I test for Buildings With an Ocean View?
A single building always has the view; Strictly decreasing heights: every building qualifies; Strictly increasing heights: only the last building qualifies; Equal heights: a building of the same height on the right blocks the view.