Buildings With an Ocean View - Practice Coding Problems

Buildings With an Ocean View - Problem

There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.

The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.

Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.

Input & Output

Example 1 — Basic Case

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

› Output: [0,2,3]

💡 Note: Building 0 (height 4) can see ocean because all buildings to its right (2,3,1) are shorter. Building 2 (height 3) can see ocean because building 3 (height 1) is shorter. Building 3 (height 1) is rightmost so it always has ocean view.

Example 2 — All Buildings Have Ocean View

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

› Output: [0,1,2,3]

💡 Note: Heights are in decreasing order, so each building can see over all buildings to its right. All buildings have ocean view.

Example 3 — Only Rightmost Has View

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

› Output: [3]

💡 Note: Building 3 (height 4) is the tallest and rightmost, so only it has ocean view. All other buildings are blocked by building 3.

Constraints

1 ≤ heights.length ≤ 10⁵
1 ≤ heights[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of building heights [4,2,3,1]

Process

Check which buildings can see ocean (no taller buildings to the right)

Output

Indices of buildings with ocean view [0,2,3]

Key Takeaway

🎯 Key Insight: Process buildings from right to left, tracking the maximum height seen so far to determine ocean view eligibility

Asked in

F Facebook 15 G Google 8 a Amazon 5

The key insight is that we can process buildings from right to left, tracking the maximum height seen so far. A building has an ocean view if it's taller than all buildings to its right. Best approach uses single pass with O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass - Track Maximum Height	O(n)	O(1)	Traverse from right to left, keeping track of the maximum height seen so far
Brute Force - Check Each Building	O(n²)	O(1)	For each building, check all buildings to its right to see if any are taller
Monotonic Stack - Right to Left	O(n)	O(n)	Traverse from right to left, maintaining a stack of building indices in decreasing height order

Single Pass - Track Maximum Height — Algorithm Steps

Start from the rightmost building (always has ocean view)
Track maximum height seen so far
For each building, if it's taller than max height, add to result
Update maximum height as we traverse

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from right

Begin with rightmost building, max height = 0

Compare and update

If current height > max, add to result and update max

Continue left

Process each building, maintaining maximum height

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* heights, int heightsSize, int* returnSize) {
    int* result = (int*)malloc(heightsSize * sizeof(int));
    *returnSize = 0;
    int maxHeight = 0;
    
    // Traverse from right to left
    for (int i = heightsSize - 1; i >= 0; i--) {
        if (heights[i] > maxHeight) {
            result[(*returnSize)++] = i;
            maxHeight = heights[i];
        }
    }
    
    // Result is in reverse order, so reverse it
    for (int i = 0; i < (*returnSize) / 2; i++) {
        int temp = result[i];
        result[i] = result[(*returnSize) - 1 - i];
        result[(*returnSize) - 1 - i] = temp;
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int heights[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            heights[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(heights, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array from right to left

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for tracking maximum height

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass - Track Maximum Height — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler