See all coding puzzles and patterns here.

Problem Definition

You given an array with $n$ numbers, representing the height of each building. The ocean is on the right, at the back of the array. Return a list of indices of the buildings with a view of the ocean.

Examples

Some test cases to verify our solution.

assert set(ocean_view([5, 4, 3, 2, 1])) == {0, 1, 2, 3, 4}
assert set(ocean_view([1, 2, 5, 2, 4, 1])) == {2, 4, 5}

Solution

We traverse backwards through the array, maintaining a minimum height for buildings in order for them to have an ocean view.

This sequence of minimum heights should be non-decreasing. I.e., the minimum height is unchanged as we encounter buildings with lower heights than the minimum necessary to view the ocean. 

def ocean_view(arr):
    cover = -1
    res = []
    for i in range(len(arr) - 1, -1, -1):
        if arr[i] > cover:
            res.append(i)
            cover = arr[i]
    return res

Complexity

Let $n = $ len(arr).

Since we are traversing the array once regardless of the input, runtime complexity should be $\Theta(n)$.

Since we are maintaining just a set of constants other than our return value, auxiliary space complexity should be $O(1)$.