Trapping Rainwater => TC -> O(N)

trappingRainWater.java

public static int trappedRW(int arr[]){
  int n=arr.length, leftMB[] = new int[n], rightMB[] = new int[n],trappedWater=0;
  leftMB[0] = arr[0];
  rightMB[n-1] = arr[n-1];
  for (int i = 1; i < n; i++) {
    leftMB[i] = Math.max(leftMB[i-1], arr[i]); 
  }
  for (int i = n-2; i >= 0; i--) {
    rightMB[i] = Math.max(rightMB[i+1],arr[i]);
  }
  for(int i=0; i<n; i++){
    int waterLevel = Math.min(leftMB[i], rightMB[i]);
    trappedWater += waterLevel - arr[i];
  }
  return trappedWater;
}