PROBLEM LINKS
DIFFICULTY
Medium-Easy
PREREQUISITES
Stack, Slopes
PROBLEM
Given n buildings at location x_i with height h_i, find out the rightmost building r_i that can be seen from the top of each building.
QUICK EXPLANATION
Maintain a stack of buildings of decreasing height from the right. When you are at building i, pop the stack until you get the highest building k such that h_k < h_i. If there is no such building, output -1. Otherwise, from that building k, repeatedly assign k := r_k while it’s not blocked from the line of sight from i. That last building will be the answer.
EXPLANATION
This problem is a classic linear version of the Art Gallery Problem. Before anything, observe that the list is already sorted, and that all positions and heights are distinct. We iterate from right to left so that we can retain information of the buildings on the right.
First, observe that the rightmost building that can be seen from i must be before any taller building after i. This is obvious since having a taller building will always block our line of sight. Let’s call such building z (if there are no taller buildings to the right, make z=n+1).
Now, observe that all buildings in the range (i, z) are smaller than building i. After all, z is already the first taller building to the right. Observation: we are guaranteed that we can see that tallest building before z from i. This is because there is no way to block the line of sight to that tallest building. Otherwise there would be a taller building to the left which will lead to a contradiction.
We start our approach from that tallest building k. Since we can already see it from i, we are confident that the rightmost building is not less than k. But k is already the tallest building that can be seen! Therefore, any building further to the right that can be seen by i can also be seen by k or any of its rightmost ancestors. But recall, we have already computed for the rightmost building of k, and that is r_k. Test if we can see r_k from i without k blocking, then assign it as k = r_k. Perform a loop on the new k while view to the next r_k is not yet blocked. Finally, assign the rightmost value r_i to the last k from the loop, then we’re done.
Implementation
An easy way to check if building is not blocking the view is by comparing the slopes of the lines determined by two pairs of buildings. Alternatively, you can also check if the signed area of the three buildings is nonnegative. Do be mindful of precision if using slopes; compare with integers as much as possible. To get the tallest building one can maintain a stack of buildings with decreasing height. Pop the stack while the last entry is smaller than the current building. The last popped entry will already be the tallest building, and after processing we push i to the stack for the next iterations.
COMPLEXITY
Though the solution may look like O(n^2) because of the extra loop, actually it’s just O(n). Whenever we loop to find the rightmost element, we skip those already traversed by other buildings between k and r_k. See the figure below for an illustration. Since each building will be traversed as r_k at most once, the total runtime is O(n).
ALTERNATIVE SOLUTIONS
You can also solve this in O(n log n) using binary search, RMQ, or similar approaches instead of a stack.
EDITORIALIST’S SOLUTION
You can find it here.