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

Posted by N.K. Chauhan on Mar 31, 2024

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


Find duplicates in O(n) time and O(n) extra space.

Maximum Product Subarray (Modified Kadane's Algorithm)

Segregate 0s and 1s in an array (Sort an array of 0s and 1s)

Minimize the difference between the heights of smallest and highest tower

Find largest sum contiguous sub-array (Kadane's Algorithm)

Find duplicates in O(n) time and O(1) extra space

Move all negative numbers to beginning of the array

Alternating +ve & -ve in array in O(1) time (maintaining order)

Program to right rotate an array by 'k' elements

Find maximum and minimum element of an array

Segregate 0s, 1s and 2s in an array (Sort an array of 0s, 1s and 2s)