Trapping Rainwater

In this article, we will solve the problem of calculating the amount of water that can be trapped after rainfall on a given map represented by an array of non-negative integers.

Example:

Input: [3, 0, 2, 0, 4]

Output: 7 

Explanation: The total water trapped between the elevations is 7 units.

• Water trapped between elevations at index 0 and 2 is 3 units.

• Water trapped between elevations at index 2 and 4 is 4 units.

Solution:

To solve this problem we can use a two-pointer approach which involves pre-computing the maximum heights to the left and right of each position. The water trapped at each position is determined by the minimum of these two values minus the height at that particular position.

Steps to Solve:

1.    Initialize Arrays:

o   Create two arrays, leftMax and rightMax, to store the maximum heights to the left and right of each position.

2.    Compute Left Max Heights:

o   Traverse the array from left to right to fill leftMax.

3.    Compute Right Max Heights:

o   Traverse the array from right to left to fill rightMax.

4.    Calculate Trapped Water:

o   Traverse the array again and for each position, calculate the water trapped as the minimum of leftMax and rightMax minus the height at that position.

Time Complexity: O(N)

Space Complexity: O(N)