Trapping Rain Water

Trapping Rain Water - LeetCode

Trapping Rain Water - GeeksforGeeks

Here is an interserting problem, the Trapping Rain Water Problem.

This problem is marked as Hard on both Leetcode and GeeksForGeeks Platform.

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.

Let understand it in simple steps:

1. Water can only be trapped if the heights on its left and right are greater than the current tower length, otherwise Not.
2. We will find out the water on top of each tower and sum the total water to get the solution.

So, First, we need to find out what is the maximum values greater on the left side of the current value and what is the maximum values greater on the right side of the current value.

we can simply find out by traversing the array and update the index if the value is greater.

public static int[] findMaxLeft(int arr[]) {
  int [] maxLeft = new int[arr.length];
  maxLeft[0] = arr[0];
  for(int i=1;i<arr.length;i++) {
   if(arr[i]>maxLeft[i-1])
    maxLeft[i]=arr[i];
   else
    maxLeft[i] = maxLeft[i-1];
  }
  return maxLeft;
 }
public static int[] findMaxRight(int arr[]) {
  int len = arr.length-1;
  int [] maxRight = new int[arr.length];
  maxRight[len] = arr[len];
  for(int i=len-1;i>=0;i--) {
   if(arr[i]>maxRight[i+1])
    maxRight[i]=arr[i];
   else
    maxRight[i] = maxRight[i+1];
  }
 }

Now we have both the Arrays leftMax and rightMax.

leftMax[] = {0 ,1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3} & rightMax[]={3, 3, 3, 3, 3, 3, 3, 3 ,2 ,2 ,2 ,1 ,6}

Now as we know Water can only be trapped on the minimum height of both the left and right sides.

In the above image, we have 5towers, say 1(height 3),2(height 0),3(height 2),4(height 0),5(height 4) water can only be trapped in Min(leftHeight, rightHeight) and also if we want to find out the water on top of any tower then :

Water = Min(leftHeight , rightHeight)- (height of current tower).

Here, Water on tower 1 = 0, Water on tower 2= 3, Water on tower 3=1, Water on tower 4=3, Water on tower 5=0.

Total water trapped = 0+3+1+3+0 = 7.

Let's Jump to the coding part:

class Solution {
    public int trap(int[] height) {
        if(height.length==0)
            return 0;
        int[] maxLeft = findMaxLeft(height);
  int[] maxRight = findMaxRight(height);
  
  int totalWater = 0;
  for(int i=0;i<height.length;i++) {
   totalWater+= Math.min(maxLeft[i], maxRight[i])-height[i];
  }
        return totalWater;
    }
     public static int[] findMaxLeft(int arr[]) {
  int [] maxLeft = new int[arr.length];
  maxLeft[0] = arr[0];
  for(int i=1;i<arr.length;i++) {
   if(arr[i]>maxLeft[i-1])
    maxLeft[i]=arr[i];
   else
    maxLeft[i] = maxLeft[i-1];
  }
  return maxLeft;
 }
 
 public static int[] findMaxRight(int arr[]) {
  int len = arr.length-1;
  int [] maxRight = new int[arr.length];
  maxRight[len] = arr[len];
  for(int i=len-1;i>=0;i--) {
   if(arr[i]>maxRight[i+1])
    maxRight[i]=arr[i];
   else
    maxRight[i] = maxRight[i+1];
  }
  return maxRight;
 }
}

Thankyou for Reading!

Happy Coding.