Buildings With an Ocean View

Picture a row of buildings facing the ocean on the right. A building sees the ocean only if nothing taller blocks it. The interviewer wants to see if you can answer this in one pass instead of checking each building against all the others. That one-pass idea is the test.

🎯 The Problem

You get a row of building heights. The ocean is to the right. Return the buildings that can see it.

• Each number is one building’s height. They stand in a row.
• The ocean sits to the right of the last building.
• A building sees the ocean if every building to its right is shorter than it.
• Return the positions of all buildings that can see the ocean.
• The positions must read left to right.
• The tallest building seen so far on the right is the running max.

Say the heights are [4, 2, 3, 1]. The last building always sees the ocean. The 3 sees over the 1. The 4 sees over everyone. The 2 is blocked by the 3. So the answer is positions 0, 2, and 3.

Input:  heights = [4, 2, 3, 1]
Output: [0, 2, 3]

Explanation:
  index 3 (height 1): nothing to its right, sees ocean
  index 2 (height 3): only a 1 to the right, sees ocean
  index 1 (height 2): a 3 to the right blocks it, no view
  index 0 (height 4): tallest of all, sees ocean

Here is the row of buildings with the ocean on the right.

🐢 Approach 1: Check Everything on the Right (Brute Force)

The idea in one line: for each building, scan all buildings to its right.

The idea:

• Take one building.
• Look at every building to its right.
• If all of them are shorter, this one sees the ocean.

How it works:

• One loop picks a building.
• A second loop scans to its right.
• Find any building taller or equal, and this one is blocked.
• Reach the end with nothing blocking, and it sees the ocean.

Why it is weak:

• For each building you scan the rest of the row.
• That is O(n²) work.
• A long row makes this slow.

Here is the brute-force code for that idea:

def find_buildings(heights):
    answer = []

    for i in range(len(heights)):
        blocked = False
        for j in range(i + 1, len(heights)):
            if heights[j] >= heights[i]:
                blocked = True
                break
        if not blocked:
            answer.append(i)

    return answer


print(find_buildings([4, 2, 3, 1]))

⚡ Approach 2: Scan Right to Left With a Running Max (Best)

The idea in one line: walk from the right and carry the tallest height seen so far.

The idea:

• A building sees the ocean only if it beats everything to its right.
• So the only thing that matters is the tallest building on the right.
• Carry that tallest height in one number as you walk backward.

How it works:

• Start a running max lower than any real height.
• Walk from the last building back to the first.
• At each building, ask: is it taller than the running max?
• If yes, nothing to its right is as tall, so record its position. Then update the running max.
• If no, something taller blocks it, so skip it.
• The positions come out right to left, so reverse the list at the end.

Why it is fast:

• One backward walk touches each building once. That is O(n).
• You carry a single number instead of rescanning the row.

Here is the dry run on [4, 2, 3, 1]. The running max starts very low.

Steps to Solve

1. Start a running max set lower than any height.
2. Walk the heights from the last index back to the first.
3. At each building, if its height is greater than the running max, it sees the ocean. Record its index.
4. Update the running max to this building’s height when it sees the ocean.
5. Reverse the collected indices so they read left to right.

#include <stdio.h>

int main(void) {
    int heights[] = {4, 2, 3, 1};
    int n = 4;

    int result[4];
    int count = 0;
    int runningMax = -1;            // lower than any height

    for (int i = n - 1; i >= 0; i--) {
        if (heights[i] > runningMax) {   // taller than all on right
            result[count++] = i;         // sees the ocean
            runningMax = heights[i];     // update the tallest seen
        }
    }

    printf("[");
    for (int j = count - 1; j >= 0; j--) {   // reverse to left-to-right
        printf("%d", result[j]);
        if (j > 0) printf(", ");
    }
    printf("]\n");
    return 0;
}

[0, 2, 3]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> findBuildings(vector<int>& heights) {
    vector<int> result;
    int runningMax = -1;            // lower than any height
    for (int i = (int)heights.size() - 1; i >= 0; i--) {
        if (heights[i] > runningMax) {   // taller than all on right
            result.push_back(i);         // sees the ocean
            runningMax = heights[i];     // update the tallest seen
        }
    }
    reverse(result.begin(), result.end());  // left-to-right order
    return result;
}

int main() {
    vector<int> heights = {4, 2, 3, 1};
    vector<int> ans = findBuildings(heights);
    cout << "[";
    for (int i = 0; i < (int)ans.size(); i++) {
        cout << ans[i];
        if (i + 1 < (int)ans.size()) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

[0, 2, 3]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class OceanView {
    static List<Integer> findBuildings(int[] heights) {
        List<Integer> result = new ArrayList<>();
        int runningMax = -1;            // lower than any height
        for (int i = heights.length - 1; i >= 0; i--) {
            if (heights[i] > runningMax) {   // taller than all on right
                result.add(i);               // sees the ocean
                runningMax = heights[i];     // update the tallest seen
            }
        }
        Collections.reverse(result);    // left-to-right order
        return result;
    }

    public static void main(String[] args) {
        int[] heights = { 4, 2, 3, 1 };
        System.out.println(findBuildings(heights));
    }
}

[0, 2, 3]

def find_buildings(heights):
    result = []
    running_max = -1               # lower than any height
    for i in range(len(heights) - 1, -1, -1):   # scan right to left
        if heights[i] > running_max:    # taller than all on right
            result.append(i)            # this building sees the ocean
            running_max = heights[i]    # update the tallest seen
    result.reverse()               # put indices in left-to-right order
    return result


heights = [4, 2, 3, 1]
print(find_buildings(heights))

[0, 2, 3]

function findBuildings(heights) {
  const result = [];
  let runningMax = -1; // lower than any height
  for (let i = heights.length - 1; i >= 0; i--) {
    if (heights[i] > runningMax) {
      // taller than all on right
      result.push(i); // this building sees the ocean
      runningMax = heights[i]; // update the tallest seen
    }
  }
  result.reverse(); // left-to-right order
  return result;
}

const heights = [4, 2, 3, 1];
console.log(findBuildings(heights));

[ 0, 2, 3 ]

Let us walk through the Python version line by line. The line running_max = -1 sets the tallest height seen so far. We start below any real height so the very first building on the right always counts. The last building has nothing to its right, so it always sees the ocean.

The loop for i in range(len(heights) - 1, -1, -1) walks from the last index back to 0. We scan right to left because the ocean is on the right. The tallest blocker for any building is whatever stands to its right, and that is what we have already passed.

The check if heights[i] > running_max is the heart of it. If the current building is taller than everything to its right, nothing blocks it. So we result.append(i) to record its position. Then running_max = heights[i] updates the tallest seen, since this building now stands between the ocean and anything further left.

The line result.reverse() flips the list. We collected the indices from right to left, so they came out as [3, 2, 0]. Reversing gives [0, 2, 3], the order the problem asks for.

⏱️ Time and Space Complexity

The brute force checks each building against all buildings on its right, so it is O(n²). The running max scan walks the array one time and updates a single number, so it is O(n). We store only the answer list, which holds at most every index once, so the extra space is O(n) for the output, or O(1) if you do not count the output.

🧩 Key Takeaways

• ✅ A building sees the ocean only if it is taller than every building to its right.
• ✅ Scan from right to left so the tallest blocker is always behind you.
• ✅ Carry one running max instead of rescanning the row each time.
• ✅ Record an index only when the building beats the running max, then update it.
• ✅ Reverse the collected indices at the end for left-to-right order.

🚀 What’s Next?

• Maximum Swap
• Continuous Subarray Sum