In trapping rain water problem, we need to find the maximum amount of water that can be trapped within given set of bars where width of each bar is 1 unit.

Input: Array containing height of bars {7, 0, 4, 2, 5, 0, 6, 4, 0, 5}

Maximum amount of water that can be trapped is 25 as shown below (in blue color).

The idea is to calculate maximum height bar on the left and right of every bar. Then the amount of water that can be stored on top of each bar is equal to minimum among maximum bar to the left and right minus height of current bar.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <bits/stdc++.h> using namespace std; // Function to find amount of water that can be trapped within // given set of bars in linear time and extra space int trap(int bars[], int n) { int water = 0; // left[i] stores the maximum height of a bar to the left // of current bar int left[n-1]; left[0] = INT_MIN; // process bars from left to right for (int i = 1; i < n - 1; i++) left[i] = max(left[i-1], bars[i-1]); /* int right[n]; right[n - 1] = INT_MIN; for (int i = n - 2; i >= 0; i--) right[i] = max(right[i+1], bars[i+1]); for (int i = 1; i < n - 1; i++) if (min(left[i], right[i]) > bars[i]) water += min(left[i], right[i]) - bars[i]; */ // right stores the maximum height of a bar to the right // of current bar int right = INT_MIN; // process bars from right to left for (int i = n - 2; i >= 1; i--) { right = max(right, bars[i+1]); // check if it is possible to store water in current bar if (min(left[i], right) > bars[i]) water += min(left[i], right) - bars[i]; } return water; } // Trapping Rain Water within given set of bars int main() { int heights[] = { 7, 0, 4, 2, 5, 0, 6, 4, 0, 5 }; int n = sizeof(heights) / sizeof(heights[0]); cout << "Maximum amount of water that can be trapped is " << trap(heights, n); return 0; } |

`Output:`

Maximum amount of water that can be trapped is 25

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

### O(1) space solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <bits/stdc++.h> using namespace std; // Function to find amount of water that can be trapped within // given set of bars in linear time and constant space int trap(int heights[], int n) { // maintain two pointers left and right pointing to leftmost and // rightmost index of the input array int left = 0, right = n-1, water = 0; int maxLeft = heights[left]; int maxRight = heights[right]; while (left < right) { if (heights[left] <= heights[right]) { left++; maxLeft = max(maxLeft, heights[left]); water += (maxLeft - heights[left]); } else { right--; maxRight = max(maxRight, heights[right]); water += (maxRight - heights[right]); } } return water; } // Trapping Rain Water within given set of bars int main() { int heights[] = { 7, 0, 4, 2, 5, 0, 6, 4, 0, 5 }; int n = sizeof(heights) / sizeof(heights[0]); cout << "Maximum amount of water that can be trapped is " << trap(heights, n); return 0; } |

`Output:`

Maximum amount of water that can be trapped is 25

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

Here’s another linear-time, constant space solution. Makes two passes, so it’s perhaps not as elegant as solution number 2 above, but it might be more intuitive to some.

Walk from left to right, keeping track of max as you go along. Any time the max changes, walk backward to the prior max, “filling with water” all intermediate bars.

Repeat, but from right to left.

Each bar is touched a constant number of times during each pass, once to compare against the max and once more to “fill with water.”

http://cpp.sh/5yf7sp

I think it needs three passes. What your algorithm return on {1,0,1}?

It would be interesting to see this problem done an a 2 dimensional array.