Arrays - Trapping Rain Water

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.

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.

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

Constraints:

n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

Solution 1 - Using temporary arrays to store maximum heights on both side, and use minimum of maximum heights to calculate how mush water can be trapped
Solution 2 - With the intution from solution 1, solve it using two pointers

The main intution behind this solution is, if you want to trap water between two heights, you can only trap upto the minimum height between those two heights. So, in this approach we are going find maximum heights on both sides for the current height, then calculate the water that can be trapped at that height as MIN(maxHeightLeft, maxHeightRight) - current height (If the current height itself is the heighest, then this may result in less than 0, in such cases we take it as 0)

In this approach, we will use a temporary array and copy last k elements of nums array into this temporary array first, then copy remaining elements from nums array, i.e. from 0^th index to n-k^th index into the temporary array. Finally replace nums array with the temporary array.

Implementation steps:

First, we will create two temporary arrays with same size as height, leftMax to store maximum heights on left side to current element, and rightMax to store maximum heights on right side to current element.
Then, run a for loop on height array from index 1 to n-1 and at every index i store max element seen so far on left side and store them in leftMax.
Next, run another for loop on height array from index n-2 to 0 and at every index i store max element seen so far on right side and store them in rightMax.
Now, run another for loop on height array, and at each index calculate the water that can be trapped as: result = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);

public class TrappingRainWater { static int trap(int[] height) { if(height.length == 0) { return 0; } int[] leftMax = new int[height.length]; int[] rightMax = new int[height.length]; int max = 0; for(int i=1; i<height.length ;i++) { max = Math.max(max, height[i-1]); leftMax[i] = max; } max=0; for(int i=height.length-2; i>=0; i--) { max = Math.max(max, height[i+1]); rightMax[i] = max; } int result =0; for(int i=0; i<height.length; i++){ result += Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]); } return result; } public static void main(String[] args) { System.out.println(trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1})); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of height array.
Space complexity: O(n) for the temporary arrays.

In this approach, we will use the intution from Solution 1 above, and notice that we are looking at minimum of two maximum elements on left and right side. So, in this approach we will use two pointers to hold maximum elements on left side and right side at the point (not necessarily the true maximum value, since we only care about minimum of those two) and apply the solution as above.

Implementation steps:

Let's declare 5 variables:
- l : left pointer for the array, initialize with 0.
- r : right pointer for the array, initialize with height.length - 1.
- leftMax : maximum element seen so far on left side, initialize with height[l].
- rightMax : maximum element seen so far on right side, initialize with height[r].
Next, run a while loop, until l and r each other, and check the following:
- If leftMax < rightMax : Increment the left pointer l, and calculate how much water can be trapped, then update the leftMax for the next element.
- If leftMax >= rightMax : Decrement the right pointer r, and calculate how much water can be trapped, then update the rightMax for the next element.

public class TrappingRainWater { static int trap(int[] height) { if(height.length == 0) { return 0; } int l=1; int r=height.length-2; int leftMax = height[l]; int rightMax = height[r]; int result =0; while(l<r) { if(leftMax < rightMax) { l++; // move left pointer result += Math.max(0, leftMax - height[l]); // leftMax is already a Min leftMax = Math.max(leftMax, height[l]);// update leftMax for next element } else { r--; // move right pointer result += Math.max(0, rightMax - height[r]); rightMax = Math.max(rightMax, height[r]); } } return result; } public static void main(String[] args) { System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of height array.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis:

Implementation steps:

Complexity Analysis: