Taller Than Everything After
Problem
A row of buildings faces the sea at the right end of the row. A building has a clear view when it is strictly taller than every building to its right. Given the heights from left to right, return the heights of the buildings with a clear view, in the same left-to-right order.
Examples
Input: heights = [16, 17, 4, 3, 5, 2]
Output: [17, 5, 2]
Why: 17 and 5 beat everything after them, and the last
building always has a viewInput: heights = [5, 5, 3]
Output: [5, 3]
Why: the first 5 is only as tall as the second one, not strictly tallerInput: heights = []
Output: []
Why: edge case, an empty row has no buildings to reportHints
0 / 3
Checking each building against everything after it compares a lot of pairs twice. Which direction of travel makes the question easy?
Walking from the right end, you only need to remember one number about the buildings you have already passed.
Scan from the last index down to the first, keeping the tallest height seen so far. A building is kept when it is taller than that maximum; update the maximum either way, and reverse the kept heights at the end.
Solution
A building's view depends only on the tallest building to its right, so scanning from the right end with a running maximum answers every building in one step. A building strictly above the running maximum is kept, and the maximum is raised to it. The kept heights come out right to left, so one reversal restores the original order. Time is O(n), and extra space is O(1) apart from the output.
def clear_views(heights):
kept, tallest = [], float("-inf")
for i in range(len(heights) - 1, -1, -1): # right to left by index
if heights[i] > tallest:
kept.append(heights[i])
tallest = heights[i]
kept.reverse() # back to left-to-right order
return kept
print(clear_views([16, 17, 4, 3, 5, 2])) # -> [17, 5, 2]
print(clear_views([5, 5, 3])) # -> [5, 3]
print(clear_views([])) # -> []Stuck on the idea rather than the code? Array Basics covers it.