You are given an array with element represents the height of a tower with width equal to one unit. It started to rain. Find the amount of water trapped between towers?

For example, tower = [0, 1, 2, 1, 3, 2, 0, 2, 3] – then answer is 6 units between towers 3 and 7.

     
          |          |  __ |   | |  __
          |       __ v |  |v_  | v_|  |
          |    __|  |__|  |  | v|  |  |
          |___|__|__|__|__|__|__|__|__|___
           0   1  2  1  3  2  0  2  3

Observe that the trapped water on top of a single tower is depends on the space on top of it. A container space will be happened to be created on top of a tower if the tower is surrounded by larger towers in bot left and right. In that sense, we need to find the leftmost and rightmost tower with height greater then current tower. Then rain accumulated on a tower is the difference between the height of minimum of these towers and the height of current tower. Let’s

     MaxLeft[i] = Maximum tower in the left of tower[i]
     MaxRight[i] = Maximum tower in the right of tower[i]

     trappedRain[i] = max{min{MaxLeft[i] , MaxRight[i]} - tower[i], 0}
     totalRain +=  trappedRain[i]

1. Scan right to left, get MaxRight[i] = index of maximum_so_far.
2. Set, MaxLeft[i]=0.
3. Scan left to right for each i:
   • Update MaxLeft[i] = index of max{max_so_far, tower[i]}
   • Trapped water on top of tower[i],
     trappedRain[i] = max{min{MaxLeft[i] , MaxRight[i]} – tower[i], 0}
     Also update the total rain.
     totalRain += trappedRain[i]
4. return totalRain

below is the simple O(n) time and O(n) space solution.

public static int accumulatedRainTotal(final int[] tower) {
    final int n = tower.length;
    final int max_right[] = new int[n];
    final int max_left[] = new int[n];

    max_right[n - 1] = tower[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        max_right[i] = Math.max(max_right[i + 1], tower[i]);
    }

    max_left[n - 1] = 0;
    int totalRain = Math.max(Math.min(max_left[0], max_right[0]) - tower[0], 0);
    for (int i = 1; i < n; i++) {
        max_left[i] = Math.max(max_left[i - 1], tower[i]);
        totalRain += Math.max(Math.min(max_left[i], max_right[i]) - tower[i], 0);
    }
    return totalRain;
}