What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

13. Trapping Rain Water • Invariant Proof & Speed-Run

Theory Context•Two Pointers & Sliding Window

HardLC 42

Trapping Rain Water (LeetCode 42)

Target Frequency:GoogleAmazonMetaAppleNetflix

You're given n non-negative integers, height, describing an elevation map made of unit-width bars side by side. Work out how much rain water would settle on top of it after a downpour.

Code / Blueprint

  Level 3 |     |     |     |     |     |     |     | [█] |     |     |     |     |
  Level 2 |     |     |     | [█] | [~] | [~] | [~] | [█] | [█] | [~] | [█] |     |
  Level 1 |     | [█] | [~] | [█] | [█] | [~] | [█] | [█] | [█] | [█] | [█] | [█] |
  --------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
    Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  | 10  | 11  |
   Height |  0  |  1  |  0  |  2  |  1  |  0  |  1  |  3  |  2  |  1  |  2  |  1  |
    Water |  -  |  -  | +1  |  -  | +1  | +2  | +1  |  -  |  -  | +1  |  -  |  -  |
 
  Legend:
  [█] = Solid elevation terrain bar (height >= 1)
  [~] = Trapped rain water (1 unit per block)
  Total Trapped Water = 1 + 1 + 2 + 1 + 1 = 6 Units

⚠️ Top Interview Gotchas:

The "Unseen Interior Peaks" Paradox: When height[left] < height[right], trapped water at left is strictly bounded by left_max. Even if an interior mountain of height 10,000 exists between them, it only acts as an even taller barrier; water at left can never exceed left_max without spilling left!
Order-of-Operations (Negative Water Trap): Always update left_max = max(left_max, height[left]) before accumulating left_max - height[left] to guarantee non-negative water.
Boundary Elements Never Trap Water: Indices 0 and n-1 can only act as outer walls, never hold water.

Worked Examples

Example 1

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

Output:6

Elevation Map & Trapped Rain WaterVisualizing Terrain Depressions, Bilateral Bounds & Water Reservoirs

Total Trapped Water = 6 Units

Elevation Bar (height[i])

Trapped Water (units)

Click any bar to inspect its exact bilateral bottleneck bounds below

Index 5 Trapped Calculation

height = 0 | left_max = 2 | right_max = 3
Water = min(2, 3) - 0 = 2 units

Bilateral Bottleneck Invariant

At any bar, water level is min(left_max, right_max). Water cannot rise higher because it would spill over the shorter side.

Two-Pointer O(1) Space Solution

If height[left] < height[right], water at left is strictly governed by left_max. We safely advance left++ without knowing interior peaks!

Top Trapping Rain Water Interview Gotchas

Unseen Interior Peaks: If h[L] < h[R], an unseen mountain of height 10,000 in the middle does not change the fact that water at L is capped by left_max. It can only spill left!
Order-of-Operations Bug: Always update left_max = max(left_max, h[L]) before subtracting to ensure you never add negative water.
Outer Edges Trap Zero: Indices 0 and n - 1 can never hold water because there are no outer containing walls.

Explanation: The elevation map (solid bars) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. Rain water accumulates in valleys between taller peaks (index 2: +1, index 4: +1, index 5: +2, index 6: +1, index 9: +1), trapping a total of 6 units.

Example 2

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

Output:9

Elevation Map & Trapped Rain WaterVisualizing Terrain Depressions, Bilateral Bounds & Water Reservoirs

Total Trapped Water = 9 Units

Elevation Bar (height[i])

Trapped Water (units)

Click any bar to inspect its exact bilateral bottleneck bounds below

Index 1 Trapped Calculation

height = 2 | left_max = 4 | right_max = 5
Water = min(4, 5) - 2 = 2 units

Bilateral Bottleneck Invariant

At any bar, water level is min(left_max, right_max). Water cannot rise higher because it would spill over the shorter side.

Two-Pointer O(1) Space Solution

If height[left] < height[right], water at left is strictly governed by left_max. We safely advance left++ without knowing interior peaks!

Top Trapping Rain Water Interview Gotchas

Unseen Interior Peaks: If h[L] < h[R], an unseen mountain of height 10,000 in the middle does not change the fact that water at L is capped by left_max. It can only spill left!
Order-of-Operations Bug: Always update left_max = max(left_max, h[L]) before subtracting to ensure you never add negative water.
Outer Edges Trap Zero: Indices 0 and n - 1 can never hold water because there are no outer containing walls.

Explanation: Water trapped between peaks totals 9 units.

⚖️Formal Constraints & Bounds

n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

Deep-Dive & Conceptual Insights

Core Insight

When height[left] < height[right], the trapped water at left is strictly bounded by left_max, regardless of any interior peaks.

Real-World Scenario & Production Applications

Terrain flood catchment simulation, civil reservoir engineering, and digital elevation model hydrology mapping.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Bilateral Envelope Boundary Initialization

Place left = 0, right = len(height) - 1. Maintain running boundary peaks left_max = 0, right_max = 0 and water = 0.

Mathematical Recurrence / Code Invariant

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

Step-by-Step Execution Trace Table

Step	`left`	`right`	`left_max`	`right_max`	Bottleneck	Water Added	Total
1	0 (h=0)	11 (h=1)	0	1	Left (`h[0] < h[11]`)	+0	0
2	1 (h=1)	11 (h=1)	1	1	Right (`h[1] >= h[11]`)	+0	0
3	1 (h=1)	10 (h=2)	1	2	Left (`h[1] < h[10]`)	+0	0
4	2 (h=0)	10 (h=2)	1	2	Left (`h[2] < h[10]`)	+1 (1 - 0)	1

Code Shape

Archetype Code Shape

Python

1	left, right = 0, len(height) - 1
2	left_max, right_max, water = 0, 0, 0
3	while left < right:
4	if height[left] < height[right]:
5	if height[left] >= left_max:
6	left_max = height[left]
7	else:
8	water += left_max - height[left]
9	left += 1
10	else:
11	if height[right] >= right_max:
12	right_max = height[right]
13	else:
14	water += right_max - height[right]
15	right -= 1
16	return water

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

The volume of water trapped above any individual bar at index $i$ is determined strictly by its confining boundaries: $\text{water}[i] = \max(0, \min(\text{max_left}, \text{max_right}) - \text{height}[i])$ . While prefix and suffix maximum arrays compute this in $O(N)$ time and $O(N)$ space, two converging pointers achieve the theoretical optimum: $O(N)$ time and $O(1)$ auxiliary space.

🏟️ The Analogy: The Leaking Bathtub

Imagine a bathtub with irregular stepped walls. Water does not care how high the tallest mountain on earth is; it spills over the lower rim of the tub. If you know with certainty that the left rim is 3 feet high and the right rim is at least 5 feet high, you can calculate the water level at the left edge immediately: water will rise to exactly 3 feet. It does not matter if the right wall is 5 feet, 10 feet, or 100 feet.

🔑 Why It Works

The cognitive leap: when height[left] < height[right], we are guaranteed that left_max < height[right] <= right_max. Therefore, min(left_max, right_max) is definitively left_max. We can safely record the water trapped at left and advance inward without ever needing to know the true value of right_max!

Calculating water before updating running max: Water trapped at left is left_max - height[left]. If you calculate water before left_max = max(left_max, height[left]), negative water values will corrupt the total.
Moving the larger boundary: You can only safely compute water at the pointer whose running boundary is strictly smaller than the opposing boundary (left_max < right_max).
Ignoring edge boundaries: Indices 0 and len(height) - 1 can never hold water; starting the two-pointer inward scan at 0 and n - 1 correctly enforces zero water on borders.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Elevation / volume trapping between boundaries with 1D heights.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: if height[left] < height[right], water at left is min(left_max, right_max) - height[left] = left_max - height[left].

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Searching for global peak: unnecessary and wastes O(N) time or space.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"I initialize left=0, right=len(height)-1, left_max=0, right_max=0. At each step, if height[left] < height[right], left is the bottleneck: I update left_max and add left_max - height[left] to water, then left++. Otherwise I do the symmetric update on right. Runs in O(N) time and O(1) space."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N)

Each iteration of the while loop advances either left or right by 1. The two pointers converge from opposite ends in exactly N steps, performing O(1) comparisons and additions per step.

SPACE COMPLEXITY

O(1) Auxiliary

Only four scalar variables are stored (left, right, left_max, right_max, and water), requiring strictly O(1) auxiliary space without auxiliary arrays or stacks.

Formal Recurrence Relation

$T(N) = N \text{ pointer steps} = O(N)$

Derivation Progression

Bottleneck Determination

$\text{if } height[L] < height[R]$

Compares outer walls in O(1) to identify which side is the governing elevation ceiling.

Water Accumulation & Step

$water += \max(0, bottleneck - height[i])$

Calculates local trapped water and steps the limiting boundary inward.

Variable Definitions

$N$

Total number of elevation bars in height array

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative

🔵 Auxiliary Heap

O(1) 4 scalar registers

🟢 Output Space

O(1) Trapped water integer

Boundary Best / Worst Cases

Best Case

$O(N)$ single inward pass.

Average Case

$O(N)$ single inward pass.

Worst Case

$O(N)$ single inward pass.

Pointer Invariant Transition Progression

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "elevation map", "compute how much water it can trap". Bilateral elevation envelope. Trapped water above bar $i$ is $\min(\max_{0 \le j \le i} H[j], \max_{i \le k < N} H[k]) - H[i]$ .

CONSTRAINTS & BOUNDS

$N \le 2 \times 10^4$ , heights $\ge 0$ . Requires $O(N)$ time and $O(1)$ space (replacing the $O(N)$ space prefix/suffix arrays with converging pointers).

FAANG PRODUCTION TRAPS & EDGE CASES

Monotonically increasing or decreasing elevation profiles (traps zero water). Updating left_max / right_max before computing trapped water prevents negative accumulation.

Theory Context•Two Pointers & Sliding Window

HardLC 42

Trapping Rain Water (LeetCode 42)

Target Frequency:GoogleAmazonMetaAppleNetflix

You're given n non-negative integers, height, describing an elevation map made of unit-width bars side by side. Work out how much rain water would settle on top of it after a downpour.

Code / Blueprint

  Level 3 |     |     |     |     |     |     |     | [█] |     |     |     |     |
  Level 2 |     |     |     | [█] | [~] | [~] | [~] | [█] | [█] | [~] | [█] |     |
  Level 1 |     | [█] | [~] | [█] | [█] | [~] | [█] | [█] | [█] | [█] | [█] | [█] |
  --------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
    Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  | 10  | 11  |
   Height |  0  |  1  |  0  |  2  |  1  |  0  |  1  |  3  |  2  |  1  |  2  |  1  |
    Water |  -  |  -  | +1  |  -  | +1  | +2  | +1  |  -  |  -  | +1  |  -  |  -  |
 
  Legend:
  [█] = Solid elevation terrain bar (height >= 1)
  [~] = Trapped rain water (1 unit per block)
  Total Trapped Water = 1 + 1 + 2 + 1 + 1 = 6 Units

⚠️ Top Interview Gotchas:

The "Unseen Interior Peaks" Paradox: When height[left] < height[right], trapped water at left is strictly bounded by left_max. Even if an interior mountain of height 10,000 exists between them, it only acts as an even taller barrier; water at left can never exceed left_max without spilling left!
Order-of-Operations (Negative Water Trap): Always update left_max = max(left_max, height[left]) before accumulating left_max - height[left] to guarantee non-negative water.
Boundary Elements Never Trap Water: Indices 0 and n-1 can only act as outer walls, never hold water.

Worked Examples

Example 1

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

Output:6

Elevation Map & Trapped Rain WaterVisualizing Terrain Depressions, Bilateral Bounds & Water Reservoirs

Total Trapped Water = 6 Units

Elevation Bar (height[i])

Trapped Water (units)

Click any bar to inspect its exact bilateral bottleneck bounds below

Index 5 Trapped Calculation

height = 0 | left_max = 2 | right_max = 3
Water = min(2, 3) - 0 = 2 units

Bilateral Bottleneck Invariant

At any bar, water level is min(left_max, right_max). Water cannot rise higher because it would spill over the shorter side.

Two-Pointer O(1) Space Solution

If height[left] < height[right], water at left is strictly governed by left_max. We safely advance left++ without knowing interior peaks!

Top Trapping Rain Water Interview Gotchas

Unseen Interior Peaks: If h[L] < h[R], an unseen mountain of height 10,000 in the middle does not change the fact that water at L is capped by left_max. It can only spill left!
Order-of-Operations Bug: Always update left_max = max(left_max, h[L]) before subtracting to ensure you never add negative water.
Outer Edges Trap Zero: Indices 0 and n - 1 can never hold water because there are no outer containing walls.

Example 2

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

Output:9

Elevation Map & Trapped Rain WaterVisualizing Terrain Depressions, Bilateral Bounds & Water Reservoirs

Total Trapped Water = 9 Units

Elevation Bar (height[i])

Trapped Water (units)

Click any bar to inspect its exact bilateral bottleneck bounds below

Index 1 Trapped Calculation

height = 2 | left_max = 4 | right_max = 5
Water = min(4, 5) - 2 = 2 units

Bilateral Bottleneck Invariant

At any bar, water level is min(left_max, right_max). Water cannot rise higher because it would spill over the shorter side.

Two-Pointer O(1) Space Solution

If height[left] < height[right], water at left is strictly governed by left_max. We safely advance left++ without knowing interior peaks!

Top Trapping Rain Water Interview Gotchas

Unseen Interior Peaks: If h[L] < h[R], an unseen mountain of height 10,000 in the middle does not change the fact that water at L is capped by left_max. It can only spill left!
Order-of-Operations Bug: Always update left_max = max(left_max, h[L]) before subtracting to ensure you never add negative water.
Outer Edges Trap Zero: Indices 0 and n - 1 can never hold water because there are no outer containing walls.

Explanation: Water trapped between peaks totals 9 units.

⚖️Formal Constraints & Bounds

n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

Deep-Dive & Conceptual Insights

Core Insight

When height[left] < height[right], the trapped water at left is strictly bounded by left_max, regardless of any interior peaks.

Real-World Scenario & Production Applications

Terrain flood catchment simulation, civil reservoir engineering, and digital elevation model hydrology mapping.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Bilateral Envelope Boundary Initialization

Place left = 0, right = len(height) - 1. Maintain running boundary peaks left_max = 0, right_max = 0 and water = 0.

Mathematical Recurrence / Code Invariant

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

Step-by-Step Execution Trace Table

Step	`left`	`right`	`left_max`	`right_max`	Bottleneck	Water Added	Total
1	0 (h=0)	11 (h=1)	0	1	Left (`h[0] < h[11]`)	+0	0
2	1 (h=1)	11 (h=1)	1	1	Right (`h[1] >= h[11]`)	+0	0
3	1 (h=1)	10 (h=2)	1	2	Left (`h[1] < h[10]`)	+0	0
4	2 (h=0)	10 (h=2)	1	2	Left (`h[2] < h[10]`)	+1 (1 - 0)	1

Code Shape

Archetype Code Shape

Python

1	left, right = 0, len(height) - 1
2	left_max, right_max, water = 0, 0, 0
3	while left < right:
4	if height[left] < height[right]:
5	if height[left] >= left_max:
6	left_max = height[left]
7	else:
8	water += left_max - height[left]
9	left += 1
10	else:
11	if height[right] >= right_max:
12	right_max = height[right]
13	else:
14	water += right_max - height[right]
15	right -= 1
16	return water

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: The Leaking Bathtub

🔑 Why It Works

Calculating water before updating running max: Water trapped at left is left_max - height[left]. If you calculate water before left_max = max(left_max, height[left]), negative water values will corrupt the total.
Moving the larger boundary: You can only safely compute water at the pointer whose running boundary is strictly smaller than the opposing boundary (left_max < right_max).
Ignoring edge boundaries: Indices 0 and len(height) - 1 can never hold water; starting the two-pointer inward scan at 0 and n - 1 correctly enforces zero water on borders.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Elevation / volume trapping between boundaries with 1D heights.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: if height[left] < height[right], water at left is min(left_max, right_max) - height[left] = left_max - height[left].

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Searching for global peak: unnecessary and wastes O(N) time or space.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"I initialize left=0, right=len(height)-1, left_max=0, right_max=0. At each step, if height[left] < height[right], left is the bottleneck: I update left_max and add left_max - height[left] to water, then left++. Otherwise I do the symmetric update on right. Runs in O(N) time and O(1) space."

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N)

Each iteration of the while loop advances either left or right by 1. The two pointers converge from opposite ends in exactly N steps, performing O(1) comparisons and additions per step.

SPACE COMPLEXITY

O(1) Auxiliary

Only four scalar variables are stored (left, right, left_max, right_max, and water), requiring strictly O(1) auxiliary space without auxiliary arrays or stacks.

Formal Recurrence Relation

$T(N) = N \text{ pointer steps} = O(N)$

Derivation Progression

Bottleneck Determination

$\text{if } height[L] < height[R]$

Compares outer walls in O(1) to identify which side is the governing elevation ceiling.

Water Accumulation & Step

$water += \max(0, bottleneck - height[i])$

Calculates local trapped water and steps the limiting boundary inward.

Variable Definitions

$N$

Total number of elevation bars in height array

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative

🔵 Auxiliary Heap

O(1) 4 scalar registers

🟢 Output Space

O(1) Trapped water integer

Boundary Best / Worst Cases

Best Case

$O(N)$ single inward pass.

Average Case

$O(N)$ single inward pass.

Worst Case

$O(N)$ single inward pass.

Pointer Invariant Transition Progression

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "elevation map", "compute how much water it can trap". Bilateral elevation envelope. Trapped water above bar $i$ is $\min(\max_{0 \le j \le i} H[j], \max_{i \le k < N} H[k]) - H[i]$ .

CONSTRAINTS & BOUNDS

$N \le 2 \times 10^4$ , heights $\ge 0$ . Requires $O(N)$ time and $O(1)$ space (replacing the $O(N)$ space prefix/suffix arrays with converging pointers).

FAANG PRODUCTION TRAPS & EDGE CASES

Monotonically increasing or decreasing elevation profiles (traps zero water). Updating left_max / right_max before computing trapped water prevents negative accumulation.

Level 3 | | | | | | | | [█] | | | | | Level 2 | | | | [█] | [~] | [~] | [~] | [█] | [█] | [~] | [█] | | Level 1 | | [█] | [~] | [█] | [█] | [~] | [█] | [█] | [█] | [█] | [█] | [█] | --------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | Height | 0 | 1 | 0 | 2 | 1 | 0 | 1 | 3 | 2 | 1 | 2 | 1 | Water | - | - | +1 | - | +1 | +2 | +1 | - | - | +1 | - | - | Legend: [█] = Solid elevation terrain bar (height >= 1) [~] = Trapped rain water (1 unit per block) Total Trapped Water = 1 + 1 + 2 + 1 + 1 = 6 Units

Step

left

right

left_max

right_max

Bottleneck

Water Added

Total

0 (h=0)

11 (h=1)

Left (h[0] < h[11])

1 (h=1)

11 (h=1)

Right (h[1] >= h[11])

1 (h=1)

10 (h=2)

Left (h[1] < h[10])

2 (h=0)

10 (h=2)

Left (h[2] < h[10])

+1 (1 - 0)

Step

left

right

left_max

right_max

Bottleneck

Water Added

Total

0 (h=0)

11 (h=1)

Left (h[0] < h[11])

1 (h=1)

11 (h=1)

Right (h[1] >= h[11])

1 (h=1)

10 (h=2)

Left (h[1] < h[10])

2 (h=0)

10 (h=2)

Left (h[2] < h[10])

+1 (1 - 0)