Daily bit(e) of C++ | Buildings with an ocean view
Daily bit(e) of C++ #308, Common interview problem: Buildings with an ocean view.
Today, we will look at a common C++ interview problem: Buildings with an ocean view.
Given an array of building heights (as std::vector<int64_t>), return a sorted list of indices of buildings with an ocean view. The ocean is on the right.
More formally, a building has an ocean view if all buildings to the right of it are smaller.
For example, for the input {1,9,6,8,6,3,3}, the output should be {1,3,4,6} because the buildings at those indexes have an ocean view.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/PKEbcKM3x.
Solution
This problem is very straightforward; however, it hinges on the knowledge of monotonic stack.
A monotonic stack will keep its elements in monotonic order, precisely what we are tasked to achieve with the output. The only hitch is that we have an indirection through indices.
So, what is a monotonic stack? When we push an element into a monotonic stack, it will first pop all elements from the top that are lower or equal. This will always keep elements in the stack in strictly decreasing order (in the context of our problem, it will keep buildings with an ocean view).
Notably, a monotonic stack remains linear in complexity:
each element enters and exits the stack at most once
total number of comparisons that lead to element eviction is, at most, the number of elements
total number of comparisons that do not lead to element eviction is, at most, the number of elements (there is at most one of these per inserted element)
As mentioned, the only remaining complexity in this problem is that we are working with indices and, therefore, need one level of indirection.
