fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3.  
  4. import java.util.Stack;
  5. /**
  6.  * 
  7.  * Prateek 
  8.  * */
  9. class TrapRainWater {
  10.  
  11. 	public static void main(String[] args) {
  12. 		//int[] bars = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
  13. 		int[] bars = {3, 0, 0, 2, 0, 4};
  14. 		System.out.println(trapWaterUsingBrute(bars));
  15. 		System.out.println(trapWaterUsingDP(bars));
  16. 		System.out.println(trapWaterUsingStack(bars));
  17. 		System.out.println(trapWaterUsingPointers(bars));
  18. 	}
  19.  
  20.  
  21. 	//Using the two pointer based approach to trap water
  22. 	static int trapWaterUsingPointers(int[] height) {
  23. 		if(height == null || height.length < 3) 
  24. 	     		return 0;
  25.  
  26. 		int l = 0, r = height.length-1; // Two pointers which will switched for movement 
  27. 		int lmax = height[0] , rmax = height[height.length-1];
  28.  
  29. 		int trappedWater = 0;
  30.  
  31. 		while (l < r) {
  32. 			if (height[l] < height[r]) {
  33. 				if (height[l] >= lmax) {  
  34. 					lmax = height[l]; //increment but dont count water
  35. 				} else {
  36. 					trappedWater += lmax - height[l];
  37. 				}
  38. 				l++;
  39. 			} else {
  40. 				if (height[r] >= rmax) {
  41. 					rmax = height[r];  //decrement but dont count water
  42. 				} else {
  43. 					trappedWater += rmax - height[r];
  44. 				}
  45. 				r--;
  46. 			}
  47. 		}
  48. 		return trappedWater;
  49. 	}
  50.  
  51.      //Stack based Approach to Trap rain water problem solution
  52.      static int trapWaterUsingStack(int[] bars) {
  53.     	 if(bars == null || bars.length < 3) 
  54.      		return 0;
  55.  
  56.     	 Stack<Integer> stack = new Stack<>();
  57.     	 stack.push(0);
  58.  
  59.     	 int len = bars.length, waterTrapped = 0;
  60.     	 for(int i=1; i < len ; i++)
  61.     	 {
  62.     		 while(!stack.isEmpty() && bars[stack.peek()] < bars[i]) {
  63.     			 int top = stack.pop();
  64.     			 if(!stack.isEmpty()) {
  65.     				 int dist = stack.isEmpty() ?  0 : i - stack.peek() - 1 ;
  66.     				 int effectiveHeight = Math.min(bars[i], bars[stack.peek()]) - bars[top];
  67.         			 waterTrapped += dist * effectiveHeight;
  68.     			 }
  69.     		 }
  70.     		 stack.push(i);
  71.     	 }
  72.     	 return waterTrapped;
  73.      }
  74.  
  75.  
  76.  	// Brute Force Approach
  77.  	static int trapWaterUsingBrute(int[] bars) {
  78.  		int len = bars.length;
  79.  		int trappedWater = 0;
  80.  		for (int i = 1; i < len - 1; i++) {
  81.  			int lmax = 0, rmax = 0;
  82.  
  83.  			for (int j = i - 1; j >= 0; j--)
  84.  				lmax = Math.max(lmax, bars[j]);
  85.  
  86.  			for (int j = i + 1; j < len; j++)
  87.  				rmax = Math.max(rmax, bars[j]);
  88.  
  89.  			trappedWater += Math.max(0, Math.min(lmax, rmax) - bars[i]);
  90.  		}
  91.  		return trappedWater;
  92.  	}
  93.  
  94.       //Dynamic Programming Apporach to Trap rain water problem solution
  95.       static int trapWaterUsingDP(int[] bars) {
  96.      	if(bars == null || bars.length < 3) 
  97.      		return 0;
  98.  
  99.      	int len = bars.length, trappedWater = 0;
  100.      	int[] left = new int[len];
  101.      	int[] right = new int[len];
  102.  
  103.      	//NB. for left most bar lmax would be 0, so counter is stated with 1,
  104.      	for(int i=1;i<len;i++) 
  105.      		left[i] = Math.max(left[i-1], bars[i-1]);
  106.  
  107.      	// similarly for right most bar rmax would be 0 at len-1. 
  108.      	for(int i= len -2 ;i >= 0;i--) 
  109.      		right[i] = Math.max(right[i+1], bars[i+1]);
  110.  
  111.  
  112.      	for(int i=0;i<len;i++)
  113.      		trappedWater += Math.max(0, Math.min(left[i], right[i]) - bars[i]);
  114.  
  115.      	return trappedWater;
  116.      }
  117.  
  118. }
  119.  
Success #stdin #stdout 0.1s 32300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10
10
10
10
https://ideone.com/5CCD63
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!