This page explains Java solution to problem Trapping Rain Water
using Array
data structure.
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Example 1:Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
package com.vc.hard;
class TrappingRainWater {
public int trap(int[] arr) {
int n = arr.length;
int left = 0;
int right = n - 1;
int res = 0;
int maxLeft = 0;
int maxRight = 0;
while(left <= right) {
if(arr[left] <= arr[right]) {
if(maxLeft < arr[left]) maxLeft = arr[left];
else res += maxLeft - arr[left];
left++;
}
else {
if(maxRight < arr[right]) maxRight = arr[right];
else res += maxRight - arr[right];
right--;
}
}
return res;
}
}
O(N)
Where N is total number of elements in an input array
O(1)