Trapping Rain Water | Leetcode 42 | Brute, Better and Optimal Solution using Stack

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.

Here’s the [Problem Link] to begin with.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Brute Solution: Prefix and Suffix Arrays

Intuition and Approach

• For each position i, find:
  • The tallest bar on the left up to i (call it prefixMax[i]).
  • The tallest bar on the right from i to the end (call it suffixMax[i]).
• Water at position i is limited by the shorter side among these two maxima.
• So, water at i = min(prefixMax[i], suffixMax[i]) − height[i].
• Add this for all positions to get the total trapped water.

Why it works:

• Water can only stand up to the height of the shorter wall among left and right sides.
• Precomputing both sides for every index makes calculation straightforward.

Code Implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height or len(height) < 3:
            return 0

        n = len(height)

        # Initialize prefixMax and suffixMax arrays.
        prefixMax = [0] * n
        suffixMax =  * n

        # Fill the prefixMax array (tallest from the left up to i).
        prefixMax = height
        for i in range(1, n):
            prefixMax[i] = max(prefixMax[i - 1], height[i])

        # Fill the suffixMax array (tallest from the right from i to end).
        suffixMax[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            suffixMax[i] = max(suffixMax[i + 1], height[i])

        # Calculate the total water trapped.
        trapped_water = 0
        for i in range(n):
            # Water at i is the difference between the limiting wall and bar height.
            trapped_water += min(prefixMax[i], suffixMax[i]) - height[i]

        return trapped_water

Code Explanation

• We first compute the tallest bar to the left for each index (prefixMax).
• Then we compute the tallest bar to the right for each index (suffixMax).
• For each index, the water is the smaller of these two heights minus the actual bar height.
• Summing across all indices gives total trapped water.

Time and Space Complexity

• Precise: Time O(n + n + n) = O(3n), Space O(2n).
• Simplified: Time O(n), Space O(n).

Conclusion

• Very easy to understand and implement.
• Uses extra memory for two arrays, but logic is simple and reliable.

Better Solution: One Suffix Array + Running Left Max

Intuition and Approach

• We can avoid storing both arrays.
• Precompute only right-side maxima in an array (rightMax).
• As we scan from left to right, keep a running leftMax.
• Water at i = min(leftMax, rightMax[i]) − height[i].

Why it works:

• You still need both left and right maxima for each position.
• The left maximum can be kept as a single number updated as we move forward.

Code Implementation

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n < 3:
            return 0

        # rightMax[i] = max(height[i..n-1])
        rightMax = [0] * n
        rightMax[-1] = height[-1]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])

        trapped = 0
        leftMax = 0
        for i in range(n):
            # Update leftMax up to current i
            leftMax = max(leftMax, height[i])
            # Water at i is limited by the lower of leftMax and rightMax[i]
            trapped += min(leftMax, rightMax[i]) - height[i]

        return trapped

Code Explanation

• We compute rightMax once by scanning from right to left.
• We maintain leftMax on the fly while scanning from left to right.
• At each index, the smaller of leftMax and rightMax[i] determines the water level.

Time and Space Complexity

• Precise: Time O(n + n) = O(2n), Space O(n).
• Simplified: Time O(n), Space O(n).

Conclusion

• Same core idea as Brute, but saves memory by avoiding the full left array.
• A nice balance between simplicity and space saving.

Optimal Solution: Two-Pointer Technique

Intuition and Approach

• The side with the smaller current height limits the water.
• Use two pointers:
  • left at the start, right at the end.
  • leftMax stores the tallest seen so far from the left.
  • rightMax stores the tallest seen so far from the right.
• Move the pointer on the smaller side inward:
  • If height[left] < height[right]:
    • If height[left] < leftMax, water += leftMax − height[left].
    • Else update leftMax.
    • Move left forward.
  • Else do the symmetric steps on the right.

Why it works:

• The water at the smaller side depends only on that side’s max, not on the far side.
• This lets us decide locally which pointer to move and how much water to add, in one pass.

Code Implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        # Edge case: If the height list is empty or has less than 3 elements, no water can be trapped.
        if not height or len(height) < 3:
            return 0

        # Initialize two pointers and variables to keep track of maximum heights.
        left, right = 0, len(height) - 1
        leftMax, rightMax = 0, 0
        trapped_water = 0

        # Traverse the elevation map using two pointers.
        while left < right:
            # Compare the heights at both pointers.
            if height[left] < height[right]:
                # Calculate water trapped at the left index.
                if height[left] >= leftMax:
                    leftMax = height[left]  # Update leftMax.
                else:
                    trapped_water += leftMax - height[left]  # Water trapped.
                left += 1  # Move left pointer to the right.
            else:
                # Calculate water trapped at the right index.
                if height[right] >= rightMax:
                    rightMax = height[right]  # Update rightMax.
                else:
                    trapped_water += rightMax - height[right]  # Water trapped.
                right -= 1  # Move right pointer to the left.

        return trapped_water

Code Explanation

• We always process the side that is shorter because that side limits the water level there.
• If the current bar on that side is lower than the recorded max for that side, the difference is the water trapped on top of that bar.
• This avoids building any extra arrays and finishes in one pass.

Time and Space Complexity

• Precise: Time O(n), Space O(1).
• Simplified: Fastest and most memory-efficient.

Conclusion

• Best approach for interviews and production use.
• Minimal memory, single scan, clean logic once you know the insight.

Final Takeaways

• Water at a position depends on the shorter of the tallest bars to its left and right.
• Brute: Two arrays (easiest to grasp).
• Better: One array + running left max (saves memory).
• Optimal: Two pointers (fastest and least memory).

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.