DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Trapping Rain Water

#algorithms #computerscience #interview #leetcode

Problem Statement

Given an array height[] where each element represents the height of a building, find the total amount of rainwater that can be trapped after raining.

Example

Input:

height = [0,1,0,2,1,0,1,3,2,1,2,1]
Enter fullscreen mode Exit fullscreen mode

Output:

6
Enter fullscreen mode Exit fullscreen mode

Brute Force Intuition (Interview Explanation)

For every building, find the tallest building on its left and the tallest building on its right.

The amount of water stored at the current index depends on the smaller of these two boundaries because water cannot exceed the shorter wall.

Water stored at index i:

min(leftMax, rightMax) - height[i]
Enter fullscreen mode Exit fullscreen mode

We repeat this process for every index and accumulate the answer.

Time Complexity 

O(NĀ²)
Enter fullscreen mode Exit fullscreen mode

Space Complexity 

O(1)
Enter fullscreen mode Exit fullscreen mode

Brute Force Java 

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int water = 0;

        for (int i = 0; i < n; i++) {

            int leftMax = 0;
            int rightMax = 0;

            for (int j = 0; j <= i; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }

            for (int j = i; j < n; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }

            water += Math.min(leftMax, rightMax) - height[i];
        }

        return water;
    }
}
Enter fullscreen mode Exit fullscreen mode

Moving Towards Optimal

In the brute force approach, we repeatedly calculate the left maximum and right maximum for every index.

Instead, we can precompute:

  • leftMax[i] = maximum height from 0 to i
  • rightMax[i] = maximum height from i to n-1

Now, for every index, the trapped water can be calculated in constant time.

This removes repeated scans and reduces the complexity from O(NĀ²) to O(N).

Optimal Approach ā€“ Prefix Max & Suffix Max

Algorithm

  1. Build the leftMax array.
  2. Build the rightMax array.
  3. For every index: 
   water += min(leftMax[i], rightMax[i]) - height[i]
Enter fullscreen mode Exit fullscreen mode
  1. Return total water.

Why It Works

Water can only stay if there is a boundary on both sides.

The maximum possible water level at any position is determined by the smaller boundary among the tallest wall on the left and the tallest wall on the right.

Therefore:

water[i] = min(leftMax[i], rightMax[i]) - height[i]
Enter fullscreen mode Exit fullscreen mode

Optimal Java Solution 

class Solution {
    public int trap(int[] height) {

        int n = height.length;
        if (n == 0) return 0;

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];

        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int trappedWater = 0;

        for (int i = 0; i < n; i++) {
            trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return trappedWater;
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run

Input:

height = [4,2,0,3,2,5]
Enter fullscreen mode Exit fullscreen mode

Left Max:

[4,4,4,4,4,5]
Enter fullscreen mode Exit fullscreen mode

Right Max:

[5,5,5,5,5,5]
Enter fullscreen mode Exit fullscreen mode
Index Height Left Max Right Max Water
0 4 4 5 0
1 2 4 5 2
2 0 4 5 4
3 3 4 5 1
4 2 4 5 2
5 5 5 5 0

Total Water:

0 + 2 + 4 + 1 + 2 + 0 = 9
Enter fullscreen mode Exit fullscreen mode

Pattern Recognition

This pattern appears whenever a problem asks for:

  • Left and right boundaries
  • Maximum constraint from both directions
  • Contribution of each index based on surrounding elements
  • Water trapping between bars

Common tools:

  • Prefix Maximum Array
  • Suffix Maximum Array
  • Two Pointer Optimization

Interview One-Liner

For every index, the water level is determined by the smaller of the tallest building on its left and right. By precomputing these boundaries using prefix and suffix maximum arrays, we can calculate trapped water for every position in O(N) time and O(N) space.

Top comments (0)