Technical Interview Question: Trapping Rain Water

You are given an array height where the element at index i represents the height of a bar. The width of each bar is assumed to be 1. You need to calculate the amount of water that can be trapped between the bars.

Write a function trappedWater(height: List[int]) -> int that returns the total units of water that can be trapped.

Example:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Note:

In this example, heights of the bars are represented by the numbers [0,1,0,2,1,0,1,3,2,1,2,1]. The water trapped between the bars is shown below:

         |
     |███|
 ████|███|

Answer:

The problem of trapping rainwater can be efficiently solved using the Two Pointers approach. Here is the step-by-step explanation:

1. Begin by initializing two pointers, left and right, to point to the first and last indices of the height array, respectively.
2. Also, initialize two variables, maxLeft and maxRight, to keep track of the maximum heights encountered from the left and right side, respectively. Set both to 0 initially.
3. Initialize a variable water to 0, which will represent the total units of water trapped.
4. Iterate until the left pointer is less than or equal to the right pointer:
   • Check if the height at the left index is less than or equal to the height at the right index.
     • If true, compare the height at the left index with maxLeft.
       • If it is greater than maxLeft, update maxLeft to the current height.
       • Otherwise, calculate the amount of water that can be trapped at the left index:
         • Add maxLeft minus the height at the left index to the water variable.
       • Increment the left pointer.
   • Otherwise, follow the same steps as above, but with the right pointer and maxRight instead.
5. Return the value of water which represents the total units of water trapped.

Here's the Python implementation of the trappedWater function:

def trappedWater(height: List[int]) -> int:
    left = 0
    right = len(height) - 1
    maxLeft = 0
    maxRight = 0
    water = 0
    
    while left <= right:
        if height[left] <= height[right]:
            if height[left] > maxLeft:
                maxLeft = height[left]
            else:
                water += maxLeft - height[left]
            left += 1
        else:
            if height[right] > maxRight:
                maxRight = height[right]
            else:
                water += maxRight - height[right]
            right -= 1
    
    return water

The time complexity of this solution is O(n), where n is the number of elements in the height array. This is because we iterate through the array only once.