Water Trapping Problem

Data Science, AI and ML
#1

Given an array arr[] of N non-negative integers which represents the height of blocks at index I, where the width of each block is 1. Compute how much water can be trapped in between blocks after raining.

Structure is like below:

| |

|_|

answer is we can trap two units of water.

Solution: We are given an array, where each element denotes the height of the block. One unit of height is equal to one unit of water, given there exists space between the 2 elements to store it. Therefore, we need to find out all such pairs that exist which can store water. We need to take care of the possible cases:

  1. There should be no overlap of water saved
  2. Water should not overflow

Therefore, let us find start with the extreme elements, and move towards the centre.

n = int(input())
arr = [int(i) for i in input().split()]
left, right = [arr[0]], [0] n
left =[arr[0]]
right = [ 0 0 0 0…0] n terms
right[n-1] = arr[-1] right most element

we use two arrays left[ ] and right[ ], which keep track of elements greater than all
elements the order of traversal respectively.

for elem in arr[1 : ]:
left.append(max(left[-1], elem) )
for i in range( len( arr)-2, -1, -1):
right[i] = max( arr[i] , right[i+1] )
water = 0
once we have the arrays left, and right, we can find the water capacity between these arrays.

for i in range( 1, n - 1):
add_water = min( left[i - 1], right[i]) - arr[i]
if add_water > 0:
water += add_water
print(water)