Sunset Views

Tags

Sunset Views

Category

Stacks

Difficulty

Medium

Problem Statement

Given an array of building heights and a direction the buildings face (east or west), return the indices of buildings that can see the sunset. A building can see the sunset if no building taller than or equal to it stands between it and the direction of the sunset. The buildings are arranged in a line from left (west) to right (east).

Intuition

A building can see the sunset only if all buildings between it and the sunset direction are strictly shorter. If the sunset is in the east, we process buildings from right to left (since the rightmost building always sees the sunset). If the sunset is in the west, we process from left to right. We track the maximum height seen so far from the sunset side. A building qualifies if it is taller than this running maximum.

Approach

  1. Determine the iteration direction based on the sunset direction:
    • East: iterate from right to left.
    • West: iterate from left to right.
  2. Maintain a variable maxHeight tracking the tallest building seen so far (from the sunset side).
  3. For each building:
    • If its height is strictly greater than maxHeight, it can see the sunset. Add its index to the result and update maxHeight.
  4. If iterating right to left, reverse the result to maintain ascending index order.

Pseudocode

function sunsetViews(buildings, direction):
    result = []
    maxHeight = 0

    if direction == "EAST":
        // rightmost buildings see sunset, iterate right to left
        for i from length(buildings) - 1 down to 0:
            if buildings[i] > maxHeight:
                result.append(i)
                maxHeight = buildings[i]
        reverse(result)
    else:  // WEST
        for i from 0 to length(buildings) - 1:
            if buildings[i] > maxHeight:
                result.append(i)
                maxHeight = buildings[i]

    return result

Time & Space Complexity

  • Time: O(n) where n is the number of buildings. Each building is visited once.
  • Space: O(n) for the result array in the worst case (e.g., strictly decreasing heights from the sunset side).

Key Insights

  • The problem can also be solved using a stack. As you iterate toward the sunset, maintain a stack of building indices. For each new building, pop all buildings from the stack that are shorter than or equal to the current building (they are now blocked). The remaining buildings in the stack at the end have sunset views.
  • The running-maximum approach is simpler and equally efficient.
  • The direction determines whether "blocking" buildings are to the left or to the right.
  • Buildings of equal height block each other.

Edge Cases

  • Empty array: return an empty result.
  • Single building: it always sees the sunset.
  • All buildings the same height: only the building closest to the sunset direction sees it.
  • Strictly increasing heights toward the sunset: only the last building (closest to sunset) sees it.
  • Strictly decreasing heights toward the sunset: every building sees the sunset.

Linked mentions