Trapping Rain Water hard

Problem Statement

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 1

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map 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

Steps to Solve

The core idea is to find, for each bar, the maximum water level that can be trapped. This maximum is determined by the maximum height of bars to its left and to its right. The amount of trapped water for a bar is the minimum of these two maximum heights minus the bar's height. We sum the trapped water for all bars to get the total trapped water.

We can solve this using two approaches:

1. Two-pointer approach (Optimized): This approach uses two pointers, one starting from the left and one from the right. We maintain the maximum height seen so far from the left and right. We move the pointer that points to the smaller maximum height.

2. Brute-force approach (Less Efficient): For each bar, iterate through the array to find the maximum height to its left and right, then calculate the trapped water. This is less efficient due to repeated iterations.

Explanation

The two-pointer approach is more efficient. It avoids redundant calculations.

1. Initialize two pointers, left and right, to the beginning and end of the height array.
2. Initialize leftMax and rightMax to 0.
3. Initialize trappedWater to 0.
4. While left < right:
   • If height[left] < height[right]:
     • Update leftMax = max(leftMax, height[left]).
     • If leftMax > height[left], it means water can be trapped at this position. Add leftMax - height[left] to trappedWater.
     • Increment left.
   • Else:
     • Update rightMax = max(rightMax, height[right]).
     • If rightMax > height[right], it means water can be trapped at this position. Add rightMax - height[right] to trappedWater.
     • Decrement right.
5. Return trappedWater.

Code (Java)

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

        while (left < right) {
            if (height[left] < height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                trappedWater += Math.max(0, leftMax - height[left]);
                left++;
            } else {
                rightMax = Math.max(rightMax, height[right]);
                trappedWater += Math.max(0, rightMax - height[right]);
                right--;
            }
        }
        return trappedWater;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the height array. We iterate through the array once using the two-pointer approach.
• Space Complexity: O(1). We use a constant amount of extra space.