Coding

Buildings With an Ocean View

Asked at

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

There are n buildings in a row. You are given an integer array heights of size n, where** **heights[i] represents the height of the i-th building. A building has an ocean view if all the buildings to its right are shorter. Return an array of indices of buildings that have an ocean view, sorted in increasing order.

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.

Input: heights = [4,3,2,1] Output: [0,1,2,3] Explanation: All the buildings have an ocean view.

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

1 <= heights.length <= 105
1 <= heights[i] <= 109

cpp

class Solution {
public:
    vector<int> findBuildings(vector<int>& heights) {
        //Your Code Goes Here
    }
};

java

class Solution {
    public List<Integer> findBuildings(int[] heights) {
       
    }
}

python

class Solution:
    def findBuildings(self, heights):

javascript

class Solution {
    findBuildings(heights) {
    
    }
}

csharp

public class Solution{
    public IList<int> FindBuildings(int[] heights){
        //your code goes here
    }
}

func findBuildings(heights []int) []int {

}

Stuck? Show a way to structure it+

01Scan buildings from right to left.
02Track the largest height seen to the right.
03Keep a building if it exceeds that maximum.
04Reverse the collected indices.

Reference answer

The rightmost building always sees the ocean. Walk right to left and maintain maxRight; a building has a view exactly when its height is greater than maxRight, then update that maximum. Collected indices arrive in reverse order, so reverse them before returning. The solution is O(n) time and O(n) output space, with O(1) working memory. Equal-height buildings to the right block the view because the condition requires all to be shorter. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

How would left-ocean view change the scan?
Tests: symmetry
Can the answer be streamed in increasing index order?
Tests: output constraints

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question