# C++ Program for Trapping Rain water problem

## Trapping Rain Water in C++

Here, in this page we  will discuss one of the famous problem of  Trapping Rain Water in C++ . We are given with n non-negative integers representing an elevation map where the width of each bar is 1, we need to compute how much water it is able to trap after raining.

Example :

• Input : arr[5] = {3, 0, 2, 0, 4}
• Output : 7
• Explanation : We can trap “3 units” of water between 3 and 2, “1 unit” on top of bar 2 and “3 units” between 2 and 4. See below diagram also.

## Method 1 :

• Take the size of the array from the user and store it in variable say n.
• Take n integers from the user and store them in an array say arr[].
• Now, iterate the entire array,
• For every i-th element, traverse the array from 0 to i and find the maximum height (a) and after that traverse the array from the i index to n, and find the maximum height (b).
• The amount of water that will be stored in this column is min(a, b) – arr[i], add this value to the total amount of water stored.
• After complete iteration print the amount of water.

### Time and Space complexity :

• Time-Complexity : O(n^2)
• Space-Complexity : O(1)

## Code for Trapping Rain Water in C++

Run
```#include<bits/stdc++.h>
using namespace std;

// Function to return the maximum
// water that can be stored
int maxWater(int arr[], int n)
{

// To store the maximum water
// that can be stored
int res = 0;

// For every element of the array
for (int i = 1; i < n-1; i++) {

// Find the maximum element on its left
int left = arr[i];
for (int j=0; j< i; j++)
left = max(left, arr[j]);

// Find the maximum element on its right
int right = arr[i];
for (int j=i+1; j< n; j++)
right = max(right, arr[j]);
// Update the maximum water
res = res + (min(left, right) - arr[i]);

}
return res;

}
// Driver code
int main()
{
int n;
cin>>n;

int arr[n];
for(int i=0; i < n; i++)
cin >> arr[i];

cout << maxWater(arr, n);

return 0;
}```
`Input : 53 0 2 0 4Output :7`

## Method 2 :

• Now, Create two array say left[] and right[] of size n.
• Create a variable say max_ and set its value to INT_MIN.
• Run one loop from 0 to n and  in each iteration update max_ as max_ = max(max_, arr[i]) and also assign left[i] = max_.
• Again, update max_ = INT_MIN.
• Run another loop from n-1 to 0 and in each iteration update max_ as max_ = max(max_, arr[i]) and also assign right[i] = max_.
• Now, traverse the array from 0 to n,
• The amount of water that will be stored in this column is min(a,b) – array[i],(where a = left[i] and b = right[i]) add this value to total amount of water stored
• After complete iteration print the amount of water.

### Time and Space complexity :

• Time-Complexity : O(n^2)
• Space-Complexity : O(1)

## Code for Trapping Rain Water in C++

Run
```#include<bits/stdc++.h>
using namespace std;

// Function to return the maximum
// water that can be stored
int maxWater(int arr[], int n)
{

// left[i] contains height of tallest bar to the
// left of i'th bar including itself
int left[n];
// Right [i] contains height of tallest bar to
// the right of ith bar including itself
int right[n];
// Initialize result
int water = 0;

// Fill left array
left[0] = arr[0];
for (int i = 1; i < n; i++)
left[i] = max(left[i - 1], arr[i]);
// Fill right array
right[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
right[i] = max(right[i + 1], arr[i]);

// Calculate the accumulated water element by element
// consider the amount of water on i'th bar, the
// amount of water accumulated on this particular
// bar will be equal to min(left[i], right[i]) - arr[i] .
for (int i = 0; i < n; i++)
water += min(left[i], right[i]) - arr[i];
return water;

} // Driver code
int main()
{
int n;
cin>>n;

int arr[n];
for(int i=0; i< n; i++)
cin>>arr[i];

cout << maxWater(arr, n);

return 0;
}```
`Input : 53 0 2 0 4Output :7`

## Method 3 :

Instead of maintaining two arrays of size n for storing the left and a right max of each i-th element, we can maintain two variables to store the maximum till that point. Since water trapped at any element = min(max_left, max_right) – arr[i]. We calculate water trapped on smaller elements out of arr[lo] and arr[hi] first and move the pointers till lo doesn’t cross hi.

### Time and Space complexity :

• Time-Complexity : O(n^2)
• Space-Complexity : O(1)

## Code for Trapping Rain Water in C++

Run
```#include<bits/stdc++.h>
using namespace std;

// Function to return the maximum
// water that can be stored
int maxWater(int arr[], int n)
{
// initialize output
int result = 0;
// maximum element on left and right
int left_max = 0, right_max = 0;
// indices to traverse the array
int lo = 0, hi = n - 1;
while (lo <= hi) {
if (arr[lo] < arr[hi])
{
if (arr[lo] > left_max)
// update max in left
left_max = arr[lo];
else
// water on curr element = max - curr
result += left_max - arr[lo];
lo++;
}
else {
if (arr[hi] > right_max)
// update right maximum
right_max = arr[hi];
else
result += right_max - arr[hi];
hi--;
}
}
return result;
}

// Driver code
int main()
{
int n;
cin>>n;

int arr[n];
for(int i=0; i < n; i++)
cin>>arr[i];

cout << maxWater(arr, n);

return 0;
}```
`Input : 53 0 2 0 4Output :7`

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription