Blog

42. Trapping Rain Water – Solution [Brute-Force to Best]

Here’s the question link on LeetCode 42. Trapping Rain Water:

https://leetcode.com/problems/trapping-rain-water/description

Brute Force O(n²)

For every index, I need to figure out how much water can be stored above it.

Think about it:

  • Find the tallest bar on the left.
  • Find the tallest bar on the right.
  • The water level at the current index will be the minimum of these two heights.
  • Subtract the current bar’s height.

So the water trapped at index i is:

water[i] = min(leftMax,rightMax)-height[i]

If this value is negative, we simply don’t add anything.

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int ans = 0;

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

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

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

            ans += min(leftMax, rightMax) - height[i];
        }

        return ans;
    }
};
42. Trapping Rain Water Brute solution

Better O(n)

The brute force approach works, but we’re repeatedly calculating the same maximum heights.

What if we calculate them once and store them?

We can maintain two arrays:

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

Now, for every index, we already know the tallest bars on both sides.

We just use:

water[i] = min(leftMax[i],rightMax[i])-height[i] 
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();

        vector<int> leftMax(n), rightMax(n);

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

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

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

        int ans = 0;

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

        return ans;
    }
};
42. Trapping Rain Water better solution

Another Approach: Monotonic Stack O(n)

There’s another interesting way to solve this using a stack.

Instead of calculating water vertically (above each bar), we can calculate it horizontally (between two walls).

The idea:

  • Keep indices in a monotonically decreasing stack.
  • Whenever we encounter a bar taller than the bar at the top of the stack, we’ve potentially found a right boundary.
  • Pop the top element. That’s the bottom of our water container.
  • If the stack isn’t empty, the new top is the left boundary.

Now we can calculate how much water fits between these boundaries.

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<int> st;
        int ans = 0;

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

            while(!st.empty() && height[i] > height[st.top()]) {

                int bottom = st.top();
                st.pop();

                if(st.empty()) break;

                int width = i - st.top() - 1;

                int h = min(height[i], height[st.top()])
                        - height[bottom];

                ans += width * h;
            }

            st.push(i);
        }

        return ans;
    }
};
42. Trapping Rain Water stack solution

Optimal O(n)

Now, can we get rid of the extra arrays and stack altogether?

Yes! We can use two pointers.

We already know that the water trapped at an index depends on the maximum height on its left and right.

Instead of calculating these maximums beforehand, we can maintain just two variables:

  • leftMax
  • rightMax

Start with two pointers, one at each end of the array.

Here’s the important observation:

The smaller side decides how much water can be trapped.

If the left side is smaller than the right side, we know the left side is the limiting boundary. We can safely calculate the water at the left pointer and move it forward.

Similarly, if the right side is smaller, process the right pointer.

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();

        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;

        int ans = 0;

        while(left < right) {

            if(height[left] < height[right]) {

                leftMax = max(leftMax, height[left]);

                ans += leftMax - height[left];

                left++;
            }
            else {

                rightMax = max(rightMax, height[right]);

                ans += rightMax - height[right];

                right--;
            }
        }

        return ans;
    }
};
42. Trapping Rain Water optimal solution

That’s it; see you in the next one.

Leave a Reply