Trapping Rain Water

LeetCode 42 | Difficulty: Hard

Hard

Problem Description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

- `n == height.length`

- `1 <= n <= 2 * 10^4`

- `0 <= height[i] <= 10^5`

Topics: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

---

Solutions

Solution 1: C# (Best: 136 ms)

Metric	Value
Runtime	136 ms
Memory	25.1 MB
Date	2019-03-30

Solution

public class Solution {
    public int Trap(int[] height) {
        int total = 0;
    int leftMax = 0, rightMax = 0;
    int a=0, b=height.Length-1;
    while(a<=b)
    {
        leftMax = Math.Max(leftMax, height[a]);
        rightMax = Math.Max(rightMax, height[b]);
        Console.WriteLine($"{leftMax} {rightMax}");
        if(leftMax<rightMax)
        {
            total += (leftMax-height[a]);
            a++;
        }
        else
        {
            total += (rightMax-height[b]);
            b--;
        }
    }
    
    return total;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Dynamic Programming	$O(n)$	$O(n)$
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?