Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 43

Trapping Rainwater: From Brute-Force to Two-Pointers

Recommended resources

Hello! In our last lesson, we tackled the 'Largest Rectangle in a Histogram' problem by transforming it into a search for boundaries (the 'next smaller element') and solving it efficiently with a monotonic stack. This highlighted a key problem-solving skill: reframing a geometric problem in terms of array properties.

Today, we'll continue this theme with another famous interview question: 'Trapping Rainwater'. Given an elevation map, your task is to calculate how much water it can hold. We will follow your preferred learning path, starting with an intuitive brute-force method, improving it with pre-computation, and finally arriving at a highly elegant and optimal two-pointer solution. This progression will not only teach you how to solve this specific problem but also showcase powerful optimization strategies.

1. Understanding the Problem

Imagine an array of non-negative integers where each number represents the height of a bar with a width of 1. If it rains, water gets trapped in the depressions formed by these bars. Our goal is to calculate the total volume of trapped water.

For example, consider the elevation map [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. The structure formed by these bars can trap 6 units of water.

An illustration of the 'Trapping Rainwater' problem. The blue area represents the water trapped between the bars (represented by the brown blocks), totaling 6 units.

The key insight for this problem is this: for any given position i, the amount of water that can be stored above it is determined by the "walls" on its left and right. Specifically, the water level at position i will rise to the height of the shorter of the two highest walls on either side.

Therefore, for any bar i, the trapped water above it can be calculated with the formula:
water[i] = min(max_height_to_the_left, max_height_to_the_right) - height[i]

The total trapped water is the sum of water[i] for all i, ensuring the result is non-negative.

Let's start by reading the formal problem statement.

Trapping Rainwater - Tutorial - takeuforward

This article from takeUforward clearly defines the problem and provides examples to solidify your understanding.

Focus on the problem statement and examples. Make sure you grasp the relationship between the input array and the volume of trapped water.

2. The Brute-Force Approach: O(n²)

The most direct way to solve the problem is to apply the formula we just derived for every single bar in the array.

The algorithm is straightforward:

  1. Initialize totalWater = 0.
  2. Iterate through each bar of the array from i = 0 to n-1.
  3. For each bar i:
    • Find the maximum height of a bar to its left, including itself (maxLeft).
    • Find the maximum height of a bar to its right, including itself (maxRight).
    • Calculate the water trapped at this position: water_i = Math.min(maxLeft, maxRight) - height[i].
    • Add this amount to totalWater.
  4. Return totalWater.

This requires two nested loops for each bar to find the left and right maximums, which is computationally expensive.

Trapping Rainwater - Tutorial - takeuforward

The takeUforward article provides a detailed walkthrough of this brute-force method, including the algorithm, illustrations, and Java code.

First, read the algorithm description. Then, review the Java code to see how the nested loops implement this logic. Finally, note the complexity analysis, which confirms this is an O(n²) solution with O(1) space.

While correct, an O(n²) solution is often too slow for the constraints of competitive programming and interviews. The bottleneck is clearly the repeated scanning for maxLeft and maxRight. How can we optimize that?

3. A Better Approach: Pre-computation with O(n) Space

Instead of re-calculating the maximums for each bar, we can pre-compute and store them. This is a classic time-space tradeoff. We can use two extra arrays to store the maximum height to the left and right of every position.

The algorithm becomes:

  1. Create a prefixMax array of size n. Traverse the height array from left to right, and for each index i, store the maximum height seen so far in prefixMax[i].
  2. Create a suffixMax array of size n. Traverse the height array from right to left, and for each index i, store the maximum height seen so far in suffixMax[i].
  3. Now, iterate through the height array one last time. For each index i, the maxLeft is prefixMax[i] and the maxRight is suffixMax[i].
  4. Calculate the total water: totalWater += Math.min(prefixMax[i], suffixMax[i]) - height[i].

This approach requires three separate passes over the array, but each pass is linear.

Trapping Rain Water Problem

This GeeksforGeeks article clearly explains the pre-computation strategy.

Read the section titled "[Better Approach] Prefix and suffix max for each index". Study the logic of creating the left[] and right[] arrays and then using them in a final loop. Pay close attention to the Java code provided, as it's a clean implementation of this idea.

This brings our time complexity down to O(n) + O(n) + O(n) = O(n), which is a great improvement. However, it comes at the cost of O(n) extra space for the two arrays. This leads to the ultimate interview follow-up: can you achieve O(n) time and O(1) space?

4. The Optimal Solution: Two-Pointer Approach

The answer is yes, and the solution is a clever application of the two-pointer technique. We can get rid of the extra arrays by calculating the trapped water on the fly as we traverse the array from both ends.

The Intuition:

Let's set up two pointers, left at the start of the array and right at the end. We'll also maintain two variables, leftMax and rightMax, which track the maximum height seen so far from the left and right ends, respectively.

The core insight is this: at any point, if leftMax < rightMax, then for the bar at the left pointer, we can be absolutely certain that the amount of water it can trap is determined by leftMax. Why? Because we know there's a wall to the right (rightMax) that is at least as high as leftMax. The true right wall for height[left] could be even taller, but it doesn't matter; the water level is capped by the smaller of the two boundary walls, which in this case is leftMax.

Symmetrically, if rightMax <= leftMax, the water trapped at the right pointer's position is determined by rightMax.

This image illustrates the core logic of the two-pointer approach. The water level at any index is determined by the minimum of the left maximum and right maximum bar heights encountered so far.

The Algorithm:

  1. Initialize left = 0, right = n-1.
  2. Initialize leftMax = 0, rightMax = 0.
  3. Initialize totalWater = 0.
  4. Loop while left < right:
    • If height[left] <= height[right]:
      • If height[left] >= leftMax, update leftMax = height[left] (this bar is a new wall, no water can be trapped on top of it).
      • Else, totalWater += leftMax - height[left] (we can trap water limited by the leftMax wall).
      • Move the pointer: left++.
    • Else (height[left] > height[right]):
      • If height[right] >= rightMax, update rightMax = height[right].
      • Else, totalWater += rightMax - height[right].
      • Move the pointer: right--.
  5. Return totalWater.

This approach processes the array in a single pass with constant extra space. To really build the intuition, let's watch a detailed explanation.

L74. Trapping Rainwater Problem | Optimal Solution & Code

In this video, Shradha Khapra provides an excellent, step-by-step walkthrough of the logic, from the initial formula to the final two-pointer optimization.

First, watch the segment explaining the pre-computation (prefix array) approach. This will reinforce the O(n) space solution. Then, and most importantly, watch the detailed explanation of the two-pointer approach. Pay close attention to her argument for why, if leftMax < rightMax, you can confidently calculate the water for the left pointer. This is the crux of the optimal solution. The dry run at the end is particularly helpful.

Now that you have a strong intuition, let's look at a clean implementation and summary of this optimal approach.

Trapping Rainwater - Tutorial - takeuforward

The takeUforward article provides a concise explanation, illustrations, and a clean Java implementation of the optimal two-pointer technique.

Read the algorithm description to see the logic laid out. Then, study the Java code that appears right after the Main class from the brute-force section. The resource seems to have a formatting issue, but the code is for the optimal solution: int n = height.length; int left = 0, right = n-1;.... Finally, review the complexity analysis, which confirms O(n) time and O(1) space.

Conclusion

In this lesson, you've mastered the 'Trapping Rainwater' problem by building up from a simple but slow solution to a highly efficient and clever one. This journey illustrates a critical aspect of algorithm design: identifying performance bottlenecks and applying different strategies—like pre-computation or two-pointers—to eliminate them.

Key Takeaways:

  • The water trapped above a bar is determined by the formula min(left_max_wall, right_max_wall) - bar_height.
  • A brute-force O(n²) solution applies this formula directly but is inefficient.
  • A better O(n) time, O(n) space solution uses prefix and suffix max arrays to avoid redundant calculations.
  • The optimal O(n) time, O(1) space solution uses a two-pointer approach, which intelligently determines which boundary (left or right) is the limiting factor at each step, allowing for on-the-fly calculation.

In our next lesson, we will tackle the 'Sliding Window Maximum' problem. This will bring us back to using specialized data structures, specifically a Deque, to solve problems that require finding maximums in a moving window. This will be another powerful tool for your interview preparation toolkit.