28. Trapping rain water

28. Trapping rain water

Problem link :- click here

package programs;

import java.util.*;

public class Array__28
{

	/*we are going to find the amount of water trapped above each elemen(wall)
	    for each element we will find the highest wall to its left
	                                              and the highest wall to its right
	     we will find the highest wall to left of each element and store it in  a array
	                                                       right    each element               another array*/   
	static int waterTrapped(int arr[], int n)
	{
		//Note :- we cannot trap water above left-most and right-most element(wall)
		if(n<3)
			return 0;
		
		//create array for left and right highest wall
		int left[]    = new int[n];
		int right[] = new int[n];
		
		//left array initialization
		left[0] = arr[0];
		for(int i=1; i<n; i++)
		{
			//we are taking maximum including that element also because we are 
			//taking the difference. so it doesn't matter
			left[i] = Math.max(left[i-1], arr[i]);
		}
		
		//right array 
		//(n-1) as we need the tallest wall to the right we are iterating from right
		right[n-1] = arr[n-1];
		for(int i=n-2; i>=0; i--)
		{
			//note :- i+1 because we want the right tallest wall
			right[i] = Math.max(right[i+1], arr[i]);
		}
		
		//Finally now we are starting the problem
		int water = 0;             //it will store amount of water trapped
		for(int i=1; i<n-1; i++)
		{
			//here we take minimum of the left and right wall 
			//and add the difference of minimum-wall and that element(wall)
			int min_height = Math.min(left[i], right[i]);
			
			//condition because there is a chance of getting the difference as negative 
			//as we let the element itself to become the left[i] or right[i]
			//and if other side is smaller than left[i] or right[i] respectively
			if(min_height-arr[i] > 0)
				water += min_height - arr[i];
		}
		return water;
	}
	
	public static void main(String[] args)
	{
		int i, n, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array : ");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array : ");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		
		System.out.println("Given array : ");
		print_array(array);

		ans = waterTrapped(array, n);
		System.out.println("\n\nRain water trapped : " + ans);
	}

	static void print_array(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n)
Space complexity :- O(n)