# Trapping Rain Water

Mon Feb 07 2022 12:22:59 GMT+0000 (UTC)

```// Efficient Method : Time Complexity : O(n), Auxilliary Space : O(n)

import java.util.*;
import java.io.*;

class GFG
{
static int getWater(int arr[], int n)
{
int res = 0;

int lMax[] = new int[n];
int rMax[] = new int[n];

lMax[0] = arr[0];
for(int i = 1; i < n; i++)
lMax[i] = Math.max(arr[i], lMax[i - 1]);

rMax[n - 1] = arr[n - 1];
for(int i = n - 2; i >= 0; i--)
rMax[i] = Math.max(arr[i], rMax[i + 1]);

for(int i = 1; i < n - 1; i++)
res = res + (Math.min(lMax[i], rMax[i]) - arr[i]);

return res;
}

public static void main(String args[])
{
int arr[] = {5, 0, 6, 2, 3}, n = 5;

System.out.println( getWater(arr, n)); // Output : 6
}
}

// Naive Method : Time Complexity : O(n^2)

static int getWater(int arr[], int n)
{
int res = 0;

for(int i = 1; i < n - 1; i++)
{
int lMax = arr[i];

for(int j = 0; j < i; j++)
lMax = Math.max(lMax, arr[j]);

int rMax = arr[i];

for(int j = i + 1; j < n; j++)
rMax = Math.max(rMax, arr[j]);

res = res + (Math.min(lMax, rMax) - arr[i]);
}

return res; // Output : 6
}```
content_copyCOPY

Trapping Rain Water Given an array arr[] of N non-negative integers representing the height of blocks. If width of each block is 1, compute how much water can be trapped between the blocks during the rainy season. Example 1: Input: N = 6 arr[] = {3,0,0,2,0,4} Output: 10 Explanation: Example 2: Input: N = 4 arr[] = {7,4,0,9} Output: 10 Explanation: Water trapped by above block of height 4 is 3 units and above block of height 0 is 7 units. So, the total unit of water trapped is 10 units. Example 3: Input: N = 3 arr[] = {6,9,9} Output: 0 Explanation: No water will be trapped. Your Task: You don't need to read input or print anything. The task is to complete the function trappingWater() which takes arr[] and N as input parameters and returns the total amount of water that can be trapped. Expected Time Complexity: O(N) Expected Auxiliary Space: O(N) Constraints: 3 < N < 10^6 0 < Ai < 10^8

https://practice.geeksforgeeks.org/problems/trapping-rain-water-1587115621/1/?track=DSASP-Arrays&batchId=190#