Trapping Rain Water

Technical Interview Question:

Given an array height representing the heights of bars in a vertical line, calculate how much rainwater can be trapped between the bars.

Write a function trapped_rainwater(height: List[int]) -> int that takes in an array of integers height and returns the total amount of rainwater that can be trapped.

Example:

>>> trapped_rainwater([0,1,0,2,1,0,1,3,2,1,2,1])
6

Answer:

To solve this problem, we can use the two-pointer approach. We will initialize two pointers, left at index 0 and right at index n-1, where n is the length of the input array.

1. Initialize the variables total_water and left_max to 0.
2. Set the variables left and right to the first and last index of the input array height.
3. While left is less than or equal to right:
   • If the value at height[left] is less than or equal to height[right]:
     • If height[left] is greater than left_max, update left_max to height[left].
     • Otherwise, add the value left_max - height[left] to total_water.
     • Increment left by 1.
   • Otherwise, if the value at height[right] is greater than left_max:
     • Update left_max to height[right].
   • Subtract height[right] from left_max and add the result to total_water.
   • Decrement right by 1.
4. Return the value of total_water.

Let's implement this approach in the trapped_rainwater function:

from typing import List

def trapped_rainwater(height: List[int]) -> int:
    total_water = 0
    left_max = 0
    left = 0
    right = len(height) - 1
    
    while left <= right:
        if height[left] <= height[right]:
            if height[left] > left_max:
                left_max = height[left]
            else:
                total_water += left_max - height[left]
            left += 1
        else:
            if height[right] > left_max:
                left_max = height[right]
            total_water += left_max - height[right]
            right -= 1
    
    return total_water

The time complexity of this solution is O(n) since we iterate over the input array only once.