Trapping Rain Water

Question

Given an elevation map, compute how much water it can trap after raining. Can be solved with two pointers, stack, or DP. A classic Google interview favorite.

Codemia · Accepted Answer

The problem of trapping rainwater can be approached using the two-pointer technique. This method applies here because we need to calculate water trapped between bars of varying heights, which requires knowing the maximum height to the left and the right of each bar. The two-pointer approach allows us to efficiently traverse the elevation map from both ends towards the center, maintaining the necessary information about the boundaries (heights) to calculate the trapped water without needing to store additional data structures.

1. Initialize two pointers, `left` at the beginning (index 0) and `right` at the end (last index) of the elevation array.
2. Create two variables, `left_max` and `right_max`, to track the maximum heights encountered from the left and right sides, respectively, initialized to 0.
3. While `left` is less than or equal to `right`:
   - If `left_max` is less than or equal to `right_max`, it means water can be trapped at the `left` index. 
     - Calculate trapped water as `left_max - height[left]` if `height[left]` is less than `left_max` and add it to a total water counter.
     - Update `left_max` to be the maximum of `left_max` and `height[left]`.
     - Move the `left` pointer one step to the right.
   - Else, do the same for the `right` index:
     - Calculate trapped water as `right_max - height[right]` if `height[right]` is less than `right_max` and add it to the total.
     - Update `right_max` to be the maximum of `right_max` and `height[right]`.
     - Move the `right` pointer one step to the left.
4. Repeat until the two pointers meet. The total water counter will hold the total amount of trapped rainwater.

Here is the Python implementation of the above approach:

```python
def trap(height):
    if not height:
        return 0

left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water_trapped = 0

while left <= right:
        if left_max <= right_max:
            water_trapped += max(0, left_max - height[left])
            left_max = max(left_max, height[left])
            left += 1
        else:
            water_trapped += max(0, right_max - height[right])
            right_max = max(right_max, height[right])
            right -= 1

return water_trapped
```
This code efficiently calculates the water trapped using the two-pointer approach.

The time complexity of this solution is O(n) because we are iterating through the elevation map once with the two pointers. The space complexity is O(1) since we are using only a constant amount of extra space (for `left_max`, `right_max`, and the water counter), regardless of the input size. This is optimal and satisfies the problem's requirement for space optimization.

1. **Flat Terrain**: If all heights are the same (e.g., `[4, 4, 4, 4]`), the output should be 0, as no water can be trapped.
2. **Single Bar**: An array with a single element (e.g., `[5]`) should also return 0, since there's no space between bars to trap water.
3. **Descending/Ascending Heights**: If the heights are in strictly descending order (e.g., `[5, 4, 3, 2, 1]`) or ascending order (e.g., `[1, 2, 3, 4, 5]`), the output should be 0, as there are no dips to hold water.
4. **Multiple Peaks and Valleys**: Input like `[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 4, 0, 0]` should return 10, as the valleys between peaks can trap water.

Trapping Rain Water

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string