Trapping Rain Water

Trapping Rain Water

What is this problem about?

The "Trapping Rain Water coding problem" is one of the most iconic challenges in algorithmic interviews. You are given an array representing an elevation map where the width of each bar is 1. You need to calculate how much water it can trap after raining. Water is trapped between two higher bars, and the amount depends on the height of the shorter of the two surrounding "walls."

Why is this asked in interviews?

This "Trapping Rain Water interview question" is asked by almost every major tech company, from Google to Goldman Sachs. It is a perfect interview problem because it can be solved in multiple ways with increasing levels of optimization: from a $O(n^2)$ brute force to $O(n)$ space-efficient solutions using dynamic programming, stacks, or two pointers. It tests a candidate's ability to optimize both time and space while maintaining clear logic.

Algorithmic pattern used

The "Array, Monotonic Stack, Two Pointers, Stack, Dynamic Programming interview pattern" offers several paths to the solution. The most efficient is the Two Pointers approach. We maintain left_max and right_max heights. By moving pointers from both ends, we can determine the water trapped at each index without needing extra space for arrays. At any point, the water trapped at the current pointer is min(left_max, right_max) - height[i].

Example explanation

Elevation: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

1. Between index 1 (height 1) and index 3 (height 2), there is a dip at index 2 (height 0).
2. Water trapped at index 2: min(1, 2) - 0 = 1 unit.
3. Between index 3 (height 2) and index 7 (height 3), there are dips at index 4, 5, 6.
4. Water at index 5: min(2, 3) - 0 = 2 units. By summing all these individual units, we get the total volume of trapped water.

Common mistakes candidates make

A common error in the "Trapping Rain Water coding problem" is not correctly identifying the boundaries for a dip. Some candidates try to use a simple "valley" check, but a valley can span multiple indices. Another mistake is in the $O(n)$ dynamic programming approach, where candidates might forget that the height of the current bar must be subtracted from the minimum of the side peaks.

Interview preparation tip

This problem is a masterclass in the "Two Pointers interview pattern." Whenever you need to calculate something based on the relative heights or values of boundaries, consider if moving from both ends towards the middle can simplify the logic. Master this problem, and you'll be well-prepared for dozens of similar "boundary" challenges.