# Java Program for Trapping Rain water problem

## Trapping Rain Water in Java

Here, in this page we  will discuss one of the famous problem of  Trapping Rain Water in Java. 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 = {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. ## Code for Trapping Rain Water in Java

Run
```public
class Main {
public
static int maxWater(int[] arr, int n) {
// To store the maximum water
// that can be stored
int res = 0;
// For every element of the array
// except first and last element

for (int i = 1; i < n - 1; i++) {
// Find maximum element on its left
int left = arr[i];
for (int j = 0; j < i; j++) {
left = Math.max(left, arr[j]);
}
// Find maximum element on its right
int right = arr[i];
for (int j = i + 1; j < n; j++) {
right = Math.max(right, arr[j]);
}
// Update maximum water value
res += Math.min(left, right) - arr[i];
}
return res;

}
// Driver code
public
static void main(String[] args) {
int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
int n = arr.length;
System.out.print(maxWater(arr, n));
}
}```
`6`

## 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.

## Code for Trapping Rain Water in Java

Run
```public class Main {
static int findWater(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 program to test above function */
public
static void main(String[] args) {
int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
int n = arr.length;
System.out.println("Maximum water that " + "can be accumulated is " + findWater(arr, n));
}
}```
`Maximum water that can be accumulated is 6`

## 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.

## Code for Trapping Rain Water in Java

Run
```public class Main {
static int arr[] = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
// Method for maximum amount of water
static int findWater(int n) {
int left[] = new int[n];
int right[] = new int[n];

// Initialize result
int water = 0;
// Fill left array
left = arr;

for (int i = 1; i < n; i++) left[i] = Math.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] = Math.max(right[i + 1], arr[i]);

for (int i = 0; i < n; i++) water += Math.min(left[i], right[i]) - arr[i];
return water;
}

// Driver method to test the above function
public
static void main(String[] args) {
System.out.println("Maximum water that can be accumulated is " + findWater(arr.length));
}
}```
`Maximum water that can be accumulated is 6`

### Related Banners

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