Daily bit(e) of C++ | Trapped water
Daily bit(e) of C++ #2, Common interview questions: Trapped water
Today we will look at a common interview question - Trapped water.
Given a 1D terrain height map (e.g. [0, 2, 3, 0, 2, 0]), determine the total amount of water that this terrain will trap.
For the above example, it would be two blocks of water.
Before you continue to read the solution, try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://godbolt.org/z/hKx7773qM.
Solution
First, let's analyze the problem. When does water get trapped in a particular space? Water gets trapped when there is terrain at this height somewhere to its left and right.
We can extend this idea to determine the height of the water at a particular coordinate. The maximum height of the water is the maximum height of the terrain on the left and right.
The actual water height is this maximum minus the terrain height at this space.
So to calculate, we need to loop over all spaces in the height map, calculating the min(left_max, right_max)-terrain.
We can calculate the left_max as we iterate over the terrain, however, we do need to precalculate right_max.
Fortunately, we have a pre-made algorithm that can do this for us. We can use std::inclusive_scan with std::max as the reduction operation. Finally, since these values need to be calculated right-to-left, we need to use reverse iterators.
Open the solution in Compiler Explorer.