Question: 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
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

An element of the array can store water if there are higher bars on the left and right. The amount of water to be stored in every element can be found out by finding the heights of bars on the left and right sides. The idea is to compute the amount of water that can be stored in every element of the array. To make this efficient one must pre-compute the highest bar on the left and right of every bar in linear time. Then use these pre-computed values to find the amount of water in every array element.

Algorithm:

• Create two array left and right of size n.
• create a variable max_ = INT_MIN.
• Run one loop from start to end.
• In each iteration update max_ as max_ = max(max_, arr[i]) and also assign left[i] = max_Update max_ = INT_MIN.
  Run another loop from end to start. In each iteration update max_ as max_ = max(max_, arr[i]) and also assign right[i] = max_
• Traverse the array from start to end.
• The amount of water that will be stored in this column is min(a,b) – array[i],(where a = left[i] and b = right[i]) add this value to total amount of water storedPrint the total amount of water stored.

Code:

/** 
* 
* @author techieExpress 
* 
* 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. 
* 
**/ 
public class findWater { 
public static int findTotalWater(int[] arr, int n) { 
	int lmax[]=new int[n]; 
	int rmax[]=new int[n]; 
	int water=0; 
	// calculate left max height of walls at each index 
	lmax[0]=arr[0]; 
	for(int i=1;i<n;i++) { 
		if(arr[i]>lmax[i-1]) { 
			lmax[i]=arr[i]; 
		} 
		else { 
			lmax[i]=lmax[i-1]; 
		} 
	} 
	// calculate right max height of walls at each index 
	rmax[n-1]=arr[n-1]; 
	for(int i=n-2;i>=0;i--) { 
		if(arr[i]>rmax[i+1]) { 
			rmax[i]=arr[i]; 
		} 
		else { 
			rmax[i]=rmax[i+1]; 
		} 
	} 
	//calculate the total amount of water at each index and add them up 
	for(int i=0;i<n;i++) { 
		water+=Math.min(lmax[i], rmax[i])-arr[i]; 
	} 
	return water; 
} 
	// Driver program 
	public static void main(String args[]) { 
		int arr[] = { 2,1,3,1,0,2}; 
		int n = arr.length; 
		System.out.println("Maximum water that can be accumulated is " + findTotalWater(arr, n)); 
		//return 0; 
	} 
} 

Detailed Explanation Video:

Git Code Link:

YouTube Channel :