Trapping Rain Water Problem

There is a very good question about Trapping Rain Water for arrays. Today I will give two solutions for this problem, Naive vs Efficient Solution. Let's understand the problem first.

Trapping Rain Water

So in the above example, you can only store a maximum of 6 units of water.

I/p= arr[] = {2,0,2}

o/p = 2 you can collect 2 Units of water in these bars. 

we are given an array of positive integers 

The elements are represented as Bars and the question is 

how much water you can store in this bar?

2nd Example :

arr[] = {3 , 0 , 1 , 2, 5 }

o/p = 6 

So now we are calculating that how much water we can

calculate suppose first is of height 3 units, 2nd bar

is of the height of 0 unit and so on ......

 if  you sum all the bars height collectively then 

 you will get the answer.

 Code ;

package dsalgo;

public class TrappingRainWaterProblem {
    // for input = arr[] = {3,0,1,2,5}
    public static void main(String[] args) {

        int arr[] = {3, 0, 1, 2, 5}, n = 5;
        System.out.println("Naive Solution:" + getWater(arr, n)); 
        System.out.println("Efficient Solution : " + 
                getWaterEfficientSolution(arr, n)); // efficient Solution
    }

    /*****Naive Solution****/
    public 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]);
        }
        System.out.println("Naive Time : " + System.nanoTime());
        return res;
    }

    public static int getWaterEfficientSolution(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]);

        System.out.println("Efficient Time::" + System.nanoTime());
        return res;
    }

}

 

Output : 

Naive Time : 2745092805500

Naive Solution:6

Efficient Time::2745093880800

Efficient Solution : 6

Just increase the input array then you will see the visible difference in Naive vs. Efficient Solution.

I tried to solve it in a simplest way.