Rain water trapping problem - O(n) time & O(n) space

Posted by N.K. Chauhan on Oct 28, 2022

Given an non-negative integer array arr[] of length n 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
Input: arr[] = {2, 1, 3, 0, 0, 2, 0}, n = 7, Output: 5


Solutions

Method 1: In O(n) time and O(n) space

A block represented by an element of the array can store water if there are higher bars on the left and the right.

Moreover, the amount of water to be stored on each block can be found by subtracting its height from the minimum of the highest bars on the left and right sides.

The idea is to iterate over the array twice, once to calculate for each element the highest bars on the left and a second time to calculate the highest bars on the left as well as the min of the two (highest bars on the left and right sides).

We can also calculate the amount of water to be stored on each block in the second loop, and if the result is positive, add it to the total water.

Complexity

The time complexity of this solution is O(n) and space complexity is O(n).

Related


Program to print Intersection of two sorted arrays

Longest substring without repeating characters

Print all Subsets (Power Set) of a given array

Merge two sorted arrays in O(1) space

Find a triplet in an array that sums to a given number

Word Break Problem (Using HashMap and DP)

Program to print Union of two sorted arrays

Count the number of inversions in an array - in O(n log n) time

Two Sum - return index of a pair of array elements with a given sum

Print all possible permutations of an Array in O(1) space