DSA · Arrays & Two Pointers · #178
Trapping Rain Water
Module 40 · difficulty 4/5·⏱ 30:00starts on first keystroke
Given `n` non-negative integers `height` representing an elevation map where the width of each bar is `1`, compute how much water it can trap after raining. Implement `function trap(height: number[]): number` that returns the total trapped water.
Examples
height = [0,1,0,2,1,0,1,3,2,1,2,1]→6— Water sits in the dips between taller bars; summed across all columns it totals 6 units.height = [4,2,0,3,2,5]→9— The 5 on the right and 4 on the left bound a basin that traps 9 units.height = [2,0,2]→2
Constraints
- · n == height.length
- · 1 <= n <= 2 * 10^4
- · 0 <= height[i] <= 10^5
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.