I came across this fun problem the other day, somewhat contrived but still fun.

Find an efficient way to store a list of all buildings on a street from where you can see the sun rise from some floor of the building. The street goes from west to east, and you can see the sun rise (early in the morning) only if you have a clear line of vision from your window to the horizon. This implies that every building to the east must be of height strictly less than your building’s height.

You are given a sequence of buildings, from west to east. Return a list of buildings from where you could possibly catch the sun rising.

Solution

Okay, so first things first - because this is a problem that has to do with validating whether things are in a certain order at its core - seems like using a stack wouldn’t be a bad idea.

Let’s initialize a stack nice_buildings that will help us here. Let’s make it so that each time we see a new building, we add the building to the nice_buildings stack.

We are going to want a way to store the height for each building as well - so let’s make it so that nice_buildings is a stack of tuples storing (building_index, height) pairs. We’ll eventually return just the building indices. For the sake of this problem, let’s assume sequence gives us nice (building_index, height) tuples.

Let’s try putting out a rough first draft.

def getNiceBuildings(sequence):
    nice_buildings = []
    for building_index, height in sequence:
        while nice_buildings and height > nice_buildings[-1][1]:
            # we want to get rid of such buildings
            nice_buildings.pop()
        nice_buildings.append((building_index, height))
    return nice_buildings

This runs with O(n) space and in time O(n). Why? How?

Well, the crucial thing to notice here - something I didn’t quite catch at first - is that we add each building to nice_buildings exactly once, and remove each building (if ever) from nice_buildings exactly once. So the total number of operations is O(n) - despite the scary nested loop.