Buildings With an Ocean View

Medium
406.

Buildings With an Ocean View

Buildings With an Ocean View is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon and Meta interviews.

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 <= 40
  • 1 <= heights[i] <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} heights
 * @return {number[]}
 */
var findBuildings = function(heights) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 40
  • 1 <= heights[i] <= 1000000000

Hints for Buildings With an Ocean View

  1. Hint 1

    Scan from the right, remembering the tallest building seen so far.

  2. Hint 2

    A building has a view exactly when it is strictly taller than that running maximum.

  3. 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

  1. For i from the end, if heights[i] > tallest, record i and update tallest.
  2. 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 out

Java

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