Solution: Trapping Rain Water

Statement

Given a sequence of non-negative integers representing the heights of bars in an elevation map, the goal is to determine the amount of rainwater that can be trapped between the bars after rain.

Constraints:

• $n ==$ heights.length

• $0 \leq$ heights[i] $\leq 10^5$

• $1 \leq n \leq 10^3$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The intuition for this problem is that to store water at any point in the elevation map, we must have higher bars on the left and right sides. The amount of water that can be stored depends on the height of these bars. The naive approach to solving this problem involves iterating over all the elements of the heights array. For each element, we look for a bar with the maximum height on its left and a bar with the maximum height on its right. Then, we take the minimum of these two heights and calculate the difference between the current element's height and the minimum value we just calculated. This difference represents the amount of water stored for an element in the elevation map.

While this approach eventually gives us the solution once all the elements have been processed, its computational cost is quite high. Because we check both the left and right parts of the array for each element, the time complexity of this approach becomes $O(n^2)$, which is exponential for larger inputs. Thus, this solution is not ideal for large datasets. Let’s explore a more efficient approach to solve this problem.

Optimized approach using two pointers

An optimized approach to solving this problem utilizes the two-pointers technique. Instead of separately processing the left and right sides for each element, we simplify it into a single iteration using two pointers, left and right, initially positioned at the elevation map's extremes. The key idea is to maintain two variables, left_max and right_max, which track the maximum heights encountered on the left and right. As the pointers move inwards, they calculate the trapped water for each bar based on the lower of the two maximum heights.

Here's the step-by-step algorithm to find the solution:

1. Start iterating the heights array using two pointers left and right. To keep track of maximum heights on the leftmost side and the rightmost side use two variables left_max and right_max.

2. If left_max is greater than right_max then it means the maximum height on the left side is greater than the maximum height on the right side.

3. Hence, we proceed to the right side and calculate the trapped water at the current right position based on right_max. Otherwise, we move on to the left side.

4. Store the amount of water that can be accumulated by taking a difference between the maximum of the respective sides (left_max or right_max) and the current bar’s height.

5. Keep iterating and updating the pointers at each step until left becomes greater than right.

Let's look at the illustration below to better understand the solution.