Trapping Rain Water

 

PROBLEM 52: Trapping Rain Water

(For best view experience, view in windows version)

Problem Reference : GeeksForGeeks

Author : Ajay Zad

Date    : 11/04/2023

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.

Solution:

class Solution:

    def trappingWater(self, arr,n):

        cnt = 0

        h = arr[len(arr)-1]

        for i in range(len(arr)-2,-1,-1):

            if arr[i] <= h:

                cnt = cnt + (h-arr[i])

            else:

                h = arr[i]

        

        i = 0 

        s = 0

        if arr[0] < h:

            while arr[i] != h:

                if arr[i] >= s:

                    s = arr[i]

                cnt = cnt + (s-arr[i])

                cnt = cnt - (h-arr[i])

                i = i + 1

        return cnt

import math

def main():

        T=int(input())

        while(T>0):

            n=int(input())

            arr=[int(x) for x in input().strip().split()]

            obj = Solution()

            print(obj.trappingWater(arr,n))

            T-=1

if __name__ == "__main__":

    main()

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.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
3 < N < 106
0 < Ai < 108