Trapping Rain water [MEDIUM]

Company:
PayU, Microsoft, De-Shaw, Amazon, Accolite

Question:

Given n non-negative integers in array representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example:
Input:
3
2 0 2
Output:
2
Structure is like below
|  |
|_|
We can trap 2 units of water in the middle gap.

Below is another example.

Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case contains an integer N followed by N numbers to be stored in array.

Output:
Print trap units of water in the middle gap.

Constraints:
1<=T<=100
3<=N<=100
0<=Arr[i]<10

Example:
Input:
2
4
7 4 0 9
3
6 9 9

Output:
10
 0
 

Code:

import java.util.*;

import java.lang.*;

import java.io.*;

class Solution {

public static void main (String[] args) {

Scanner sc = new Scanner(System.in);

    int m = sc.nextInt();

    for(int mi=0;mi<m;mi++){

        int n = sc.nextInt();

        int [] ar = new int [n];

        for(int i=0;i<n;i++){

            ar[i]=sc.nextInt();

        }

        System.out.println(find_res(ar,n));

    }

}

public static int find_res(int arr[], int n){

    int []left = new int [n];

    int []right = new int [n];

    int water =0;

    left[0]= arr[0];

    for (int i = 1; i < n; i++)

           left[i] = Math.max(left[i-1], arr[i]);

    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;

    }

}

Execution Time: 0.12


Execution Time: 0.72 because only one array used

	#python code
	def find_water_trapped(a,size):
	right = ['None'] * size
	right[size - 1] = a[size - 1]
	lis = reversed(range(0,size - 1))
	for i in lis:
	right[i] = max(right[i+1],a[i])
	trapped_water,temp = 0,0
	for i in range(1,size-1):
	temp = max(temp,max(a[i-1],a[i]))
	trapped_water += min(right[i],temp) - a[i]
	print(trapped_water)
	t = int(input())
	for i in range(t):
	n = int(input())
	s = input()
	arr = list(map(int,s.split()))
	find_water_trapped(arr,len(arr))

view raw Trap Rain Water hosted with ❤ by GitHub