Trapping Rain Water

Are you stuck on the LeetCode problem “Trapping Rain Water“? Don’t worry; we’ve got you covered. Trapping rainwater is a classic problem that many programmers struggle with, but once you understand the approach, it becomes much simpler. In this blog post, we will discuss multiple approaches to solve this problem – from bruteforce to dynamic programming, stack-based solutions to two-pointer techniques. We have also provided code solutions in C++, Java, and Python for each of these approaches to help you better understand how they work. By the end of this post, you’ll not only be familiar with the various techniques used to solve this problem, but also be ready to tackle similar problems with ease. So let’s dive in!

Understanding the Trapping Rain Water Problem

In the trapping rain water problem, we are given an array representing an elevation map where the width of each bar is 1. The problem statement is to compute the volume of water that can be trapped between these bars after a heavy rainstorm above elevation map.

The basic idea is to determine how much rainwater units of rain water can be gathered in the valleys formed between these elevation bars and the black section.

Source: LeetCode

In the image above, the elevation array is [0,1,0,2,1,0,1,3,2,1,2,1], and the total trapped rainwater is 6 ans.

LeetCode Problem #42: Trapping Rain Water

We will now explore the exact statement of LeetCode problem #42, which requires you to do the following:

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example:

Input: Array height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

One of the simplest approaches to solve the trapping rain water problem is the bruteforce approach. In this method, we calculate the water trapped at each bar individually by finding the heights of the left and right boundaries. By iterating through each bar, we can calculate the amount of water trapped between them using the blue section class solution.

1. Start by iterating through each bar of the given histogram from left to right.
2. For each bar, determine the height of the left boundary by finding the maximum height of the bars to the left of it.
3. Similarly, determine the height of the right boundary by finding the maximum height of the bars to the right of it.
4. Calculate the height of the water trapped at the current bar by taking the minimum of the left and right boundaries and subtracting the height of the current bar.
5. If the calculated height is negative, it means there is no water trapped at that bar, so set the trapped water height to 0.
6. Add the calculated trapped water height to a running total to keep track of the total trapped water.
7. Repeat steps 2-6 for each bar.
8. At the end of the iteration, the running total will represent the total amount of water trapped between the bars of the histogram.
9. This brute force approach may take longer to compute for larger histograms, but it provides a straightforward solution to the problem.

C++ Implementation of Bruteforce Approach

int trap(vector<int>& height) {
    int trapped_water = 0;
    int size = height.size();

    for (int i = 1; i < size - 1; i++) {
        int max_left = 0, max_right = 0;

        for (int j = i; j >= 0; j--)
            max_left = max(max_left, height[j]);

        for (int j = i; j < size; j++)
            max_right = max(max_right, height[j]);

        trapped_water += min(max_left, max_right) - height[i];
    }

    return trapped_water;
}


Java Implementation of Bruteforce Approach

public int trap(int[] height) {
    int trappedWater = 0;
    int size = height.length;

    for (int i = 1; i < size - 1; i++) {
        int maxLeft = 0, maxRight = 0;

        for (int j = i; j >= 0; j--)
            maxLeft = Math.max(maxLeft, height[j]);

        for (int j = i; j < size; j++)
            maxRight = Math.max(maxRight, height[j]);

        trappedWater += Math.min(maxLeft, maxRight) - height[i];
    }

    return trappedWater;
}


Python Implementation of Bruteforce Approach

def trap(height):
    trapped_water = 0
    size = len(height)

    for i in range(1, size-1):
        max_left = max_right = 0

        for j in range(i, -1, -1):
            max_left = max(max_left, height[j])

        for j in range(i, size):
            max_right = max(max_right, height[j])

        trapped_water += min(max_left, max_right) - height[i]

    return trapped_water


Dynamic Programming Approach for Trapping Rain Water

1. The trapping rain water problem involves calculating the amount of water that can be trapped between bars in a given elevation map.
2. The dynamic programming (DP) approach helps optimize the calculation by reducing redundant calculations.
3. To use DP, we start by precomputing the maximum heights on the left and right side of each bar and store them in arrays. This means, for each bar, we find the maximum height of the bar to its left and the maximum height of the bar to its right.
4. By precomputing and storing these maximum heights in arrays, we eliminate the need to repeatedly calculate them during the actual water trapping calculation. This step is done to minimize redundant calculations and improve efficiency.
5. Once we have the maximum heights arrays, we can calculate the trapped water for each bar in a single pass.
6. In this single pass, we iterate over each bar and calculate the height of trapped water by finding the minimum value between the maximum height on the left and the maximum height on the right. This minimum value represents the height at which water can be trapped.
7. We subtract the bar’s own height from the calculated minimum value to obtain the height of trapped water for that particular bar.
8. We accumulate the height of trapped water for each bar and get the total trapped water for the entire elevation map.
9. By using this DP approach, we can solve the trapping rain water problem with optimal space complexity and without unnecessary calculations.

Overall, the dynamic programming approach for the trapping rain water problem involves precomputing maximum heights on the left and right side of each bar, storing them in arrays, and then using these arrays to calculate the trapped water for each bar in a single pass. This approach helps reduce redundant calculations and improves efficiency.

C++ Implementation of DP Approach

int trap(vector<int>& height) {
    int trapped_water = 0;
    int size = height.size();

    vector<int> max_left(size, 0);
    vector<int> max_right(size, 0);

    max_left[0] = height[0];
    max_right[size-1] = height[size-1];

    for (int i = 1; i < size; i++)
        max_left[i] = max(max_left[i-1], height[i]);

    for (int i = size-2; i >= 0; i--)
        max_right[i] = max(max_right[i+1], height[i]);

    for (int i = 1; i < size-1; i++)
        trapped_water += min(max_left[i], max_right[i]) - height[i];

    return trapped_water;
}


Java Implementation of DP Approach

public int trap(int[] height) {
    int trappedWater = 0;
    int size = height.length;

    int[] maxLeft = new int[size];
    int[] maxRight = new int[size];

    maxLeft[0] = height[0];
    maxRight[size-1] = height[size-1];

    for (int i = 1; i < size; i++)
        maxLeft[i] = Math.max(maxLeft[i-1], height[i]);

    for (int i = size-2; i >= 0; i--)
        maxRight[i] = Math.max(maxRight[i+1], height[i]);

    for (int i = 1; i < size-1; i++)
        trappedWater += Math.min(maxLeft[i], maxRight[i]) - height[i];

    return trappedWater;
}


Python Implementation of DP Approach

def trap(height):
    trapped_water = 0
    size = len(height)

    max_left = [0] * size
    max_right = [0] * size

    max_left[0] = height[0]
    max_right[size-1] = height[size-1]

    for i in range(1, size):
        max_left[i] = max(max_left[i-1], height[i])

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

    for i in range(1, size-1):
        trapped_water += min(max_left[i], max_right[i]) - height[i]

    return trapped_water


Using Stacks for Trapping Rain Water

Another approach to solve the trapping rain water problem involves using stacks. The stack allows us to keep track of the consecutive bars with non-decreasing heights. Whenever we encounter a bar with a greater height, we can calculate the trapped water between the current bar and the previous bar on the stack. One popular algorithm that uses this approach is the rightmax algorithm.

C++ Implementation Using Stacks

int trap(vector<int>& height) {
    int trapped_water = 0;
    int size = height.size();
    stack<int> st;

    for (int i = 0; i < size; i++) {
        while (!st.empty() && height[i] > height[st.top()]) {
            int top = st.top();
            st.pop();

            if (!st.empty()) {
                int distance = i - st.top() - 1;
                int bounded_height = min(height[i], height[st.top()]) - height[top];
                trapped_water += distance * bounded_height;
            }
        }

        st.push(i);
    }

    return trapped_water;
}


Java Implementation Using Stacks

public int trap(int[] height) {
    int trappedWater = 0;
    int size = height.length;
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < size; i++) {
        while (!stack.empty() && height[i] > height[stack.peek()]) {
            int top = stack.pop();

            if (!stack.empty()) {
                int distance = i - stack.peek() - 1;
                int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
                trappedWater += distance * boundedHeight;
            }
        }

        stack.push(i);
    }

    return trappedWater;
}


Python Implementation Using Stacks

def trap(height):
    trapped_water = 0
    size = len(height)
    stack = []

    for i in range(size):
        while stack and height[i] > height[stack[-1]]:
            top = stack.pop()

            if stack:
                distance = i - stack[-1] - 1
                bounded_height = min(height[i], height[stack[-1]]) - height[top]
                trapped_water += distance * bounded_height

        stack.append(i)

    return trapped_water


Two Pointers Approach for Trapping Rain Water

The two pointers approach is an efficient method that allows us to solve the trapping rain water problem in a single iteration. This technique maintains two pointers, one starting from the left side and the other from the right side of the elevation array. By moving the pointers towards each other, we update the maximum heights on both sides and calculate the trapped water at each position. The time complexity of this algorithm is O(n), making it a highly efficient solution for the leftmax problem.

C++ Implementation Using Two Pointers

int trap(vector<int>& height) {
    int trapped_water = 0;
    int size = height.size();

    int left = 0, right = size-1;
    int max_left = 0, max_right = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] > max_left)
                max_left = height[left];
            else
                trapped_water += max_left - height[left];

            left++;
        }
        else {
            if (height[right] > max_right)
                max_right = height[right];
            else
                trapped_water += max_right - height[right];

            right--;
        }
    }

    return trapped_water;
}


Java Implementation Using Two Pointers

public int trap(int[] height) {
    int trappedWater = 0;
    int size = height.length;

    int left = 0, right = size-1;
    int maxLeft = 0, maxRight = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] > maxLeft)
                maxLeft = height[left];
            else
                trappedWater += maxLeft - height[left];

            left++;
        }
        else {
            if (height[right] > maxRight)
                maxRight = height[right];
            else
                trappedWater += maxRight - height[right];

            right--;
        }
    }

    return trappedWater;
}


Python Implementation Using Two Pointers

def trap(height):
    trapped_water = 0
    size = len(height)

    left, right = 0, size-1
    max_left, max_right = 0, 0

    while left < right:
        ifheight[left] < height[right]:
            if height[left] > max_left:
                max_left = height[left]
            else:
                trapped_water += max_left - height[left]
            left += 1
        else:
            if height[right] > max_right:
                max_right = height[right]
            else:
                trapped_water += max_right - height[right]
            right -= 1

    return trapped_water


Final Thoughts

The trapping rain water problem is a versatile coding interview question that tests both your problem-solving skills and knowledge of data structures and algorithms. This article provides an in-depth analysis of the trapping rain water LeetCode solution, focusing on the two-pointer approach, Python implementation, and best practices for solving the problem efficiently using the n-1 approach.

Keep practicing similar problems and make use of the tips and techniques provided in this article to enhance your problem-solving abilities and prepare for coding interview success.