Facebook Pixel

42. Trapping Rain Water

Problem Description

You are given an array of n non-negative integers where each integer represents the height of a bar in an elevation map. Each bar has a width of 1 unit. Your task is to calculate how much rainwater can be trapped between the bars after it rains.

The water gets trapped between bars when there are taller bars on both sides that can act as walls. For any position i, water can be trapped above it if there exists a taller bar somewhere to its left and another taller bar somewhere to its right. The amount of water that can be trapped at position i is determined by the minimum height of the tallest bars on both sides minus the height of the current bar.

For example, if you have heights [0,1,0,2,1,0,1,3,2,1,2,1], the total trapped water would be 6 units. Water fills in the valleys created by the elevation differences, but only up to the level constrained by the shorter of the two surrounding peaks.

The solution uses dynamic programming to pre-compute two arrays:

  • left[i]: stores the maximum height from the start up to position i
  • right[i]: stores the maximum height from position i to the end

For each position, the water level above it is min(left[i], right[i]), and the actual water trapped is min(left[i], right[i]) - height[i]. The total trapped water is the sum of water at all positions.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To understand how water gets trapped, imagine looking at each bar individually. At any given position, water can only be held if there are taller "walls" on both sides. The water level at that position will be determined by the shorter of these two walls - water would overflow from the shorter side if we tried to fill it higher.

Think of it like filling a bathtub - the water level can't exceed the height of the lowest wall. For each position i, we need to know:

  1. What's the tallest bar to my left (including myself)?
  2. What's the tallest bar to my right (including myself)?

The water level above position i would be min(max_left, max_right). Since the bar itself takes up space, the actual water trapped is min(max_left, max_right) - height[i].

The key insight is that we can pre-compute these maximum heights efficiently. Instead of checking all bars to the left and right for each position (which would be inefficient), we can build two arrays in linear time:

  • Build left[] by scanning from left to right, where left[i] = max(left[i-1], height[i])
  • Build right[] by scanning from right to left, where right[i] = max(right[i+1], height[i])

This way, we calculate each maximum only once and reuse the results. The pattern here is that the maximum height up to position i is either the bar at position i itself or the maximum we've seen so far before position i. This dynamic programming approach reduces our time complexity from O(n²) to O(n).

Learn more about Stack, Two Pointers, Dynamic Programming and Monotonic Stack patterns.

Solution Approach

The implementation uses dynamic programming with two auxiliary arrays to efficiently compute the trapped water.

Step 1: Initialize the arrays

  • Create left array initialized with height[0] repeated n times
  • Create right array initialized with height[-1] repeated n times
  • These arrays will store the maximum heights from left and right respectively

Step 2: Build the maximum height arrays The algorithm fills both arrays in a single loop from i = 1 to n-1:

  • For left[i]: Calculate max(left[i-1], height[i])

    • This gives us the maximum height from position 0 to position i
    • We build this left-to-right since each position depends on the previous one
  • For right[n-i-1]: Calculate max(right[n-i], height[n-i-1])

    • This gives us the maximum height from position n-i-1 to position n-1
    • We build this right-to-left by using index manipulation n-i-1

Step 3: Calculate trapped water Using Python's zip() function to iterate through all three arrays simultaneously:

  • For each position, calculate min(left[i], right[i]) - height[i]
  • min(left[i], right[i]) gives the water level at position i
  • Subtracting height[i] gives the actual water trapped above the bar
  • Sum all these values to get the total trapped water

Time Complexity: O(n) - We make two passes through the array (one for building the arrays, one for calculating the sum)

Space Complexity: O(n) - We use two additional arrays of size n to store the maximum heights

The elegance of this solution lies in pre-computing the required information, allowing us to calculate the trapped water at each position in constant time during the final summation.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with heights [3, 0, 2, 0, 4] to see how the solution works.

Initial Setup:

  • Array: [3, 0, 2, 0, 4]
  • n = 5
  • Initialize left = [3, 3, 3, 3, 3] (all set to height[0])
  • Initialize right = [4, 4, 4, 4, 4] (all set to height[-1])

Step 1: Build the maximum height arrays

Building left[] (max height from left up to position i):

  • i = 1: left[1] = max(left[0], height[1]) = max(3, 0) = 3
  • i = 2: left[2] = max(left[1], height[2]) = max(3, 2) = 3
  • i = 3: left[3] = max(left[2], height[3]) = max(3, 0) = 3
  • i = 4: left[4] = max(left[3], height[4]) = max(3, 4) = 4
  • Result: left = [3, 3, 3, 3, 4]

Building right[] (max height from position i to the end):

  • i = 1, pos = 3: right[3] = max(right[4], height[3]) = max(4, 0) = 4
  • i = 2, pos = 2: right[2] = max(right[3], height[2]) = max(4, 2) = 4
  • i = 3, pos = 1: right[1] = max(right[2], height[1]) = max(4, 0) = 4
  • i = 4, pos = 0: right[0] = max(right[1], height[0]) = max(4, 3) = 4
  • Result: right = [4, 4, 4, 4, 4]

Step 2: Calculate trapped water at each position

For each position, water trapped = min(left[i], right[i]) - height[i]:

Positionheightleftrightmin(left, right)Water Trapped
033433 - 3 = 0
103433 - 0 = 3
223433 - 2 = 1
303433 - 0 = 3
444444 - 4 = 0

Total water trapped = 0 + 3 + 1 + 3 + 0 = 7 units

Visual representation:

     |
     |≈≈≈|
 |≈≈≈|||
 |||||
 |_|_|_|_|
 3 0 2 0 4

Where represents trapped water. The water fills the valleys between the bars, with the level capped by the minimum of the tallest bars on each side.

Solution Implementation

1class Solution:
2    def trap(self, height: List[int]) -> int:
3        """
4        Calculate the amount of water that can be trapped after raining.
5      
6        Args:
7            height: List of non-negative integers representing elevation map
8          
9        Returns:
10            Total amount of trapped rainwater
11        """
12        n = len(height)
13      
14        # Initialize arrays to store maximum height to the left and right of each position
15        left_max = [0] * n
16        right_max = [0] * n
17      
18        # Base cases: first element for left_max, last element for right_max
19        left_max[0] = height[0]
20        right_max[n - 1] = height[n - 1]
21      
22        # Fill left_max array: for each position, store the maximum height seen so far from the left
23        for i in range(1, n):
24            left_max[i] = max(left_max[i - 1], height[i])
25      
26        # Fill right_max array: for each position, store the maximum height seen so far from the right
27        for i in range(n - 2, -1, -1):
28            right_max[i] = max(right_max[i + 1], height[i])
29      
30        # Calculate trapped water at each position
31        # Water level at position i = min(left_max[i], right_max[i])
32        # Trapped water = water level - height of bar at position i
33        total_water = 0
34        for i in range(n):
35            water_level = min(left_max[i], right_max[i])
36            total_water += water_level - height[i]
37      
38        return total_water
39
1class Solution {
2    public int trap(int[] height) {
3        // Get the length of the height array
4        int n = height.length;
5      
6        // Arrays to store the maximum height to the left and right of each position
7        int[] leftMax = new int[n];
8        int[] rightMax = new int[n];
9      
10        // Initialize the first element of leftMax and last element of rightMax
11        leftMax[0] = height[0];
12        rightMax[n - 1] = height[n - 1];
13      
14        // Fill both arrays in a single pass
15        // leftMax[i] stores the maximum height from index 0 to i
16        // rightMax[i] stores the maximum height from index i to n-1
17        for (int i = 1; i < n; i++) {
18            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
19            rightMax[n - i - 1] = Math.max(rightMax[n - i], height[n - i - 1]);
20        }
21      
22        // Calculate the total trapped water
23        int totalWater = 0;
24        for (int i = 0; i < n; i++) {
25            // Water trapped at position i is determined by the minimum of
26            // the maximum heights on both sides minus the current height
27            totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
28        }
29      
30        return totalWater;
31    }
32}
33
1class Solution {
2public:
3    int trap(vector<int>& height) {
4        int n = height.size();
5      
6        // Arrays to store the maximum height to the left and right of each position
7        vector<int> leftMax(n), rightMax(n);
8      
9        // Initialize the first and last elements
10        leftMax[0] = height[0];
11        rightMax[n - 1] = height[n - 1];
12      
13        // Build the maximum height arrays
14        // leftMax[i] = maximum height from index 0 to i
15        // rightMax[i] = maximum height from index i to n-1
16        for (int i = 1; i < n; ++i) {
17            leftMax[i] = max(leftMax[i - 1], height[i]);
18            rightMax[n - i - 1] = max(rightMax[n - i], height[n - i - 1]);
19        }
20      
21        // Calculate the total trapped water
22        int totalWater = 0;
23        for (int i = 0; i < n; ++i) {
24            // Water level at position i is determined by the minimum of
25            // the maximum heights on both sides
26            // Trapped water = water level - ground height
27            totalWater += min(leftMax[i], rightMax[i]) - height[i];
28        }
29      
30        return totalWater;
31    }
32};
33
1/**
2 * Calculates the amount of water that can be trapped after raining
3 * given an elevation map represented by an array of heights.
4 * 
5 * @param height - Array representing the elevation map where each element is the height of a bar
6 * @returns The total amount of trapped rainwater
7 */
8function trap(height: number[]): number {
9    const n: number = height.length;
10  
11    // Array to store the maximum height to the left of each position (including itself)
12    const leftMax: number[] = new Array<number>(n).fill(height[0]);
13  
14    // Array to store the maximum height to the right of each position (including itself)
15    const rightMax: number[] = new Array<number>(n).fill(height[n - 1]);
16  
17    // Build the leftMax and rightMax arrays
18    // leftMax[i] = maximum height from index 0 to i
19    // rightMax[i] = maximum height from index i to n-1
20    for (let i: number = 1; i < n; i++) {
21        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
22        rightMax[n - i - 1] = Math.max(rightMax[n - i], height[n - i - 1]);
23    }
24  
25    // Calculate the total trapped water
26    let totalWater: number = 0;
27    for (let i: number = 0; i < n; i++) {
28        // Water level at position i is determined by the minimum of 
29        // the maximum heights on both sides
30        // Trapped water = water level - ground height
31        totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
32    }
33  
34    return totalWater;
35}
36

Time and Space Complexity

The time complexity is O(n), where n is the length of the input array height. This is because:

  • The initialization of left and right arrays takes O(n) time
  • The for loop iterates through the array once with n-1 iterations, performing constant time operations (max comparisons and assignments) in each iteration, resulting in O(n) time
  • The final sum operation with zip iterates through all n elements once, performing constant time operations (min comparison and subtraction) for each element, which is O(n) time
  • Overall: O(n) + O(n) + O(n) = O(n)

The space complexity is O(n), where n is the length of the input array height. This is because:

  • Two auxiliary arrays left and right are created, each of size n, requiring O(n) space each
  • The zip operation in the return statement creates an iterator but doesn't create additional arrays
  • Total auxiliary space: O(n) + O(n) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Edge Case: Empty or Single Element Array

A frequent oversight is not handling arrays with length 0 or 1, which can cause index out of bounds errors when initializing left_max[0] or right_max[n-1].

Problem Code:

def trap(self, height: List[int]) -> int:
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n
    left_max[0] = height[0]  # IndexError if height is empty
    right_max[n - 1] = height[n - 1]

Solution: Add an early return for arrays that cannot trap water:

def trap(self, height: List[int]) -> int:
    n = len(height)
    if n <= 2:  # Cannot trap water with fewer than 3 bars
        return 0
  
    left_max = [0] * n
    right_max = [0] * n
    # ... rest of the code

2. Incorrect Loop Bounds When Building Arrays

Mixing up the loop boundaries or indices when filling the right_max array is a common mistake, especially when trying to build both arrays in a single loop.

Problem Code:

# Attempting to fill both arrays in one loop incorrectly
for i in range(1, n):
    left_max[i] = max(left_max[i-1], height[i])
    right_max[n-i] = max(right_max[n-i+1], height[n-i])  # Off-by-one error

Solution: Keep the loops separate for clarity, or carefully manage indices:

# Separate loops (clearer)
for i in range(1, n):
    left_max[i] = max(left_max[i-1], height[i])

for i in range(n-2, -1, -1):
    right_max[i] = max(right_max[i+1], height[i])

# Or combined with correct indices
for i in range(1, n):
    left_max[i] = max(left_max[i-1], height[i])
    right_max[n-i-1] = max(right_max[n-i], height[n-i-1])

3. Memory Optimization Confusion

When attempting the two-pointer optimization to reduce space complexity from O(n) to O(1), developers often incorrectly update the pointers or water calculation logic.

Problem Code:

# Incorrect two-pointer implementation
left, right = 0, n - 1
left_max = right_max = 0
total = 0

while left < right:
    if height[left] < height[right]:
        total += left_max - height[left]  # May add negative water
        left_max = max(left_max, height[left])
        left += 1

Solution: Update the maximum before calculating water, and ensure non-negative water:

while left < right:
    if height[left] < height[right]:
        left_max = max(left_max, height[left])
        total += max(0, left_max - height[left])  # Or update after max calculation
        left += 1
    else:
        right_max = max(right_max, height[right])
        total += max(0, right_max - height[right])
        right -= 1
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More