Buildings with Ocean view

1762.Buildings With an Ocean View

Array

Stack

Monotonic Stack

Problem Statement:

There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings. An ocean view exists for a building if all buildings to its right are shorter. Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in ascending order.

Example:

Input:

heights = [4,2,3,1]

→

Output:

[0,2,3]

Java Solution:

// Super easy stack solution just pop heights that don't have 
// ocean view. (Remember constraint only traverse forward)
public int[] findBuildings(int[] heights) {
    Stack<Integer> s = new Stack<>();

    // Maintain a monotonic stack of building indices
    for (int i = 0; i < heights.length; i++) {
        // Pop shorter buildings that lose ocean view
        while (!s.isEmpty() && heights[s.peek()] < heights[i])
            s.pop();
        s.push(i);
    }

    // Convert stack to array in ascending order
    int[] res = new int[s.size()];
    for (int i = res.length - 1; i >= 0; i--)
        res[i] = s.pop();

    return res;
}

Python Solution:

def findBuildings(self, heights: List[int]) -> List[int]:
    stack = []
    
    for i in range(len(heights)):
        # Remove buildings that lose ocean view
        while stack and heights[stack[-1]] < heights[i]:
            stack.pop()
        stack.append(i)
    
    return stack

C++ Solution:

class Solution {
public:
    vector<int> findBuildings(vector<int>& heights) {
        stack<int> s;
        
        for(int i = 0; i < heights.size(); i++) {
            while(!s.empty() && heights[s.top()] < heights[i])
                s.pop();
            s.push(i);
        }
        
        vector<int> result;
        while(!s.empty()) {
            result.insert(result.begin(), s.top());
            s.pop();
        }
        
        return result;
    }
};

Complexity:

Time: O(n) | Space: O(n)