Trapping Rain Water – 42. LeetCode

To solve the LeetCode problem “Trapping Rain Water”, we’re given an array representing an elevation map, where each element’s value is the height of that point. The goal is to calculate how much water can be trapped between the bars after it rains. Think of each bar as a wall, and the water as filling in the gaps between them.

Problem Analysis

Water can only be trapped between two taller bars. For each position, the amount of water above it depends on the height of the tallest bar to its left and the tallest bar to its right.

Two Pointer Approach

The two-pointer approach is optimal here because:

1. Efficient Calculations: Instead of using additional space to store left and right maximum height, we calculate them dynamically as we we traverse both ends toward each other.
2. Low Complexity: This method minimizes both time and space complexity by avoiding the need for extra arrays or repeated calculations, which would make the solution slower or require more memory.
3. Pattern: This is a two pointer technique that works well in scenarios where comparisons from both ends of a sequence are needed, commonly seen in problems that deal with partitioning or simultaneous traversal.

The brute force approach would involve checking each bar individually, requiring nested loops and resulting in O(n^2) time complexity. The two-pointer approach is superior because it:

• Eliminates nested loops, making it more efficient.

• Uses constant space by maintaining minimal variables, improving space complexity.

Solution

1. Initialize two pointers (left at start and right at end)
2. Track the max heights encountered from both ends (leftMax and rightMax).
3. Calculate the trapped water at each position based on the lower of the two heights.
4. Move pointers inward until they meet, updating the trapped water and maximum heights along the way.

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int waterTrapped = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left]; // Update left max
            } else {
                waterTrapped += leftMax - height[left]; // Calculate water above this bar
            }
            left++; // Move left pointer inward
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right]; // Update right max
            } else {
                waterTrapped += rightMax - height[right]; // Calculate water above this bar
            }
            right--; // Move right pointer inward
        }
    }
    return waterTrapped;
}

Line By Line Explanation

1. Initialize Variables

int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int waterTrapped = 0;

• left and right are pointers starting from the ends of the array
• leftMax and rightMax keep track of the highest bars seen so far from the left and right
• waterTrapped stores the total amount of water.

2. Loop Until Pointers Meet

while (left < right) {

• The loop continues until the left and right pointers meet, covering all bars in the array.

3. Compare Height

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

• We determine which side is lower.
• This choice ensures that we move the pointer with the lower height. This approach leverages the key insight that the trapped water at any point is limited by the shorter boundary between the left and right sides.

4. Left Side Calculations

if (height[left] >= leftMax) {
    leftMax = height[left]; // Update left max
} else {
    waterTrapped += leftMax - height[left]; // Calculate water above this bar
}
left++; // Move left pointer inward

• If the current height at the left pointer is greater than or equal to leftMax, we update leftMax
• If it’s less, we calculate how much water can be trapped above the current height (using leftMax – height[left]) and add that to totalWater
• We then move pointer toward center
• The water that can be trapped above a bar depends on the shorter of the tallest bars to its left and right.

6. Right Side Calcuations

if (height[right] >= rightMax) {
    rightMax = height[right]; // Update right max
} else {
    waterTrapped += rightMax - height[right]; // Calculate water above this bar
}
right--; // Move right pointer inward

• If height[right] is greater than or equal to rightMax, we update rightMax.
• Otherwise, water can be trapped, calculated as rightMax – height[right]
• We then move right inward.

6. Return Total Water Trapped

return waterTrapped;

• The loop exits once left meets right, and waterTrapped contains the total water trapped between bars.

Why This Code is Structured This Way

• Efficient Updates: By updating leftMax and rightMax as we move inward, we efficiently determine the possible water level based on the lower of the two sides.

• Minimal Variables: We use only essential variables, ensuring constant space.

• Clear Flow: The if-else structure clearly handles both sides symmetrically, allowing us to compute trapped water in a linear pass.

This approach is efficient for the “Trapping Rain Water” problem, as it minimizes both time and space complexity while maintaining clarity.