Trapping Rain Water

Leetcode 42 – Trapping Rain Water | Two Pointer

by

Problem Description:

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 (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
Problem Link :Trapping Rain Water – LeetCode
Solution(s):
Approach 1: Brute Force Solution
Java Code:
public int trap(int[] height) {
    int maxWater=0;
    int leftMax=0,rightMax=0;
    for(int i=1;i<height.length-1;i++) {
	//find max from left of height[i]
	leftMax=height[i];
	for(int j=0;j<i;j++) {
	  leftMax = Math.max(leftMax, height[j]);
	}			

	//find max from right of height[i]
	rightMax=height[i];
	for(int j=i+1;j<height.length;j++) {
	  rightMax = Math.max(rightMax, height[j]);
	}
			
	// Update maximum water value
	maxWater += Math.min(leftMax, rightMax) - height[i];
      }
     return maxWater;
}

Explanation:

1.Initialization:

  • maxWater: This accumulates the total amount of water trapped between the heights.
  • leftMax, rightMax: These variables store the maximum height values to the left and right of each current index i.

2.Main Loop:

  • The loop starts from i = 1 to height.length - 2, skipping the first and last bars (since no water can be trapped outside the array).

3.Finding Maximum Height to the Left:

  • For each i, a nested loop runs from 0 to i - 1 to find the maximum height (leftMax) among all heights left of height[i].

4.Finding Maximum Height to the Right:

  • Similarly, another nested loop runs from i + 1 to the end of the array to find the maximum height (rightMax) among all heights right of height[i].

5.Calculating Water at Index i:

  • For each index i, the trapped water is determined by the difference between the smaller of the two maximum heights (leftMax and rightMax) and the current height (height[i]).
  • This difference is added to maxWater.

6.Final Result:

  • After the loop completes, the total amount of trapped water is stored in maxWater and returned as the result.
Complexity:
  • Time-Complexity: O(n²) because for each element i, two nested loops are used to find leftMax and rightMax, both running in O(n). Hence, the total time complexity is O(n) * O(n) = O(n²).
  • Space-Complexity: O(1)

Optimization Opportunity:

This brute-force approach can be optimized by using dynamic programming or the two-pointer technique, reducing the time complexity to O(n). The version I shared earlier using the two-pointer technique is one such optimization.

Approach 2: Using Two Pointers
  • Create two pointers leftPtr and rightPtr and two other variables maxLeft and maxRight
  • Loop until leftPtr and rightPtr meet.
  • If hight[leftPtr] is smaller or equal to height[rightPtr],
  • then if height[leftPtr] is less than equal to maxLeft, update maxLeft to height[leftPtr] else add the difference between maxLeft and height[leftPtr] to result. and move leftPtr to right.
  • else, if height[leftPtr] is greater than height[rightPtr],
  • then if height[rightPtr] is greater than equal to maxRight, update maxRight to height[rightPtr] else add the difference between maxRight and height[rightPtr] to result. and move rightPtr to left.
  • return the result
Java Code:
public int trap(int[] height) {
        int n = height.length;

        //left and right pointers
        int leftPtr = 0;
        int rightPtr = n-1;

        int result = 0;

        int maxleft = 0;
        int maxright = 0;

        // loop until left and right pointers meet
        while(leftPtr <= rightPtr){

            // if height[left] is smaller or equal to height[right]
            if(height[leftPtr] <= height[rightPtr]){
                if(height[leftPtr] >= maxleft){
                    maxleft = height[leftPtr];
                }
                
                else{
                    result += maxleft - height[leftPtr];
                }
                leftPtr++; 
            }
            // if height[left] is greater than height[right]
            else{
                if(height[rightPtr] >= maxright){
                    maxright = height[rightPtr];
                }
                else{
                     result += maxright - height[rightPtr];
                }
                rightPtr--;
            }
        }
        return result;  
    }
Complexity:
  • Time-Complexity: O(n)
  • Space-Complexity:O(1)

Related posts:

Master Two Pointer Technique: A Complete Guide
Leetcode 189 - Rotate Array | Three Approaches
Leetcode 88- Merge Sorted Array | Two Pointer

Leave a comment