Trapping Rain Water

▶

Steps

setup

Initialize pointers and variables

Set left pointer at index 0 and right pointer at index 11 (end of array). Initialize left_max, right_max, and water to 0.

💡 Starting pointers at both ends allows scanning inward to find trapped water efficiently.

Line:

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

💡 We prepare to compare heights from both ends to decide which pointer to move.

compare

Compare heights at pointers

Compare height at left (0) and right (1). Since 0 < 1, we will move the left pointer inward.

💡 Moving the pointer at the smaller height side ensures trapped water is bounded correctly.

Line:

if height[left] < height[right]:

💡 The smaller height side limits trapped water, so we process that side first.

shrink

Process left pointer: update left_max or add trapped water

Since height[left] (0) is equal to left_max (0), update left_max to 0. No water trapped here.

💡 left_max tracks the highest bar seen so far from the left to calculate trapped water.

Line:

if height[left] >= left_max:
    left_max = height[left]
else:
    water += left_max - height[left]

💡 We update left_max to reflect the highest boundary on the left side.

move_left

Move left pointer inward

Increment left pointer from 0 to 1 to continue scanning from the left side.

💡 Moving the pointer inward progresses the scan and allows checking the next bar.

Line:

left += 1

💡 Pointer movement is essential to traverse the array and find trapped water.

compare

Compare heights at pointers

Compare height at left (1) and right (1). Since 1 is not less than 1, move right pointer inward.

💡 When heights are equal or left is not smaller, move the right pointer to process that side.

Line:

if height[left] < height[right]:

💡 Choosing which pointer to move depends on relative heights to ensure correct trapped water calculation.

shrink

Process right pointer: update right_max or add trapped water

Since height[right] (1) is greater than or equal to right_max (0), update right_max to 1. No water trapped here.

💡 right_max tracks the highest bar seen so far from the right to calculate trapped water.

Line:

if height[right] >= right_max:
    right_max = height[right]
else:
    water += right_max - height[right]

💡 Updating right_max sets the boundary for trapping water on the right side.

move_right

Move right pointer inward

Decrement right pointer from 11 to 10 to continue scanning from the right side.

💡 Moving the pointer inward progresses the scan and allows checking the next bar.

Line:

right -= 1

💡 Pointer movement is essential to traverse the array and find trapped water.

shrink_and_move_left

Process left pointer steps combined

Process multiple left pointer steps: update left_max or add trapped water, then move pointer inward repeatedly until pointer reaches index 9.

💡 Combining repeated similar steps reduces verbosity while preserving clarity.

Line:

while left < right and height[left] < height[right]:
    if height[left] >= left_max:
        left_max = height[left]
    else:
        water += left_max - height[left]
    left += 1

💡 This loop accumulates trapped water on the left side and moves the pointer inward efficiently.

compare

Compare heights at pointers

Compare height at left (1) and right (2). Since 1 < 2, move left pointer inward.

💡 Moving the pointer at the smaller height side ensures trapped water is bounded correctly.

Line:

if height[left] < height[right]:

💡 The smaller height side limits trapped water, so we process that side first.

move_left

Move left pointer inward to meet right pointer

Increment left pointer from 9 to 10. Now left equals right, so loop ends.

💡 When pointers meet or cross, the scan is complete.

Line:

left += 1

💡 Traversal ends when pointers meet, ensuring all trapped water is counted.

reconstruct

Return total trapped water

Pointers have met; return the accumulated trapped water total, which is 6 units.

💡 The final result is the sum of all trapped water calculated during traversal.

Line:

return water

💡 The algorithm efficiently computes trapped water in one pass using two pointers.

def trap(height):
    left, right = 0, len(height) - 1  # STEP 1
    left_max, right_max = 0, 0  # STEP 1
    water = 0  # STEP 1
    while left < right:  # STEP 2
        if height[left] < height[right]:  # STEP 2
            if height[left] >= left_max:  # STEP 3
                left_max = height[left]  # STEP 3
            else:
                water += left_max - height[left]  # STEP 8
            left += 1  # STEP 8
        else:
            if height[right] >= right_max:  # STEP 6
                right_max = height[right]  # STEP 6
            else:
                water += right_max - height[right]
            right -= 1
    return water  # STEP 11

if __name__ == '__main__':
    print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # Output: 6

📊

Trapping Rain Water - Watch the Algorithm Execute, Step by Step

Watching the pointers move and how trapped water accumulates visually reveals the logic behind the two-pointer approach, making the algorithm intuitive without needing to parse code alone.

setup

left

0

0

1

1

0

2

2

3

1

4

0

5

1

6

3

7

2

8

1

9

2

10

right

1

11

Result: 0

compare

left

0

0

1

1

0

2

2

3

1

4

0

5

1

6

3

7

2

8

1

9

2

10

right

1

11

Result: 0

shrink

left

0

0

1

1

0

2

2

3

1

4

0

5

1

6

3

7

2

8

1

9

2

10

right

1

11

Result: 0

move_left

0

0

left

1

1

0

2

2

3

1

4

0

5

1

6

3

7

2

8

1

9

2

10

right

1

11

Result: 0

compare

0

0

left

1

1

0

2

2

3

1

4

0

5

1

6

3

7

2

8

1

9

2

10

right

1

11

Result: 0

shrink

0

0

left

1

1

0

2

2

3

1

4

0

5

1

6

3

7

2

8

1

9

2

10

right

1

11

Result: 0

move_right

0

0

left

1

1

0

2

2

3

1

4

0

5

1

6

3

7

2

8

1

9

right

2

10

1

11

Result: 0

record

0

0

1

1

0

2

2

3

1

4

0

5

1

6

3

7

2

8

left

1

9

right

2

10

1

11

Result: 6

compare

0

0

1

1

0

2

2

3

1

4

0

5

1

6

3

7

2

8

left

1

9

right

2

10

1

11

Result: 6

move_left

0

0

1

1

0

2

2

3

1

4

0

5

1

6

3

7

2

8

1

9

right

2

10

1

11

Result: 6

reconstruct

0

0

1

1

0

2

2

3

1

4

0

5

1

6

3

7

2

8

1

9

right

2

10

1

11

Result: 6

Key Takeaways

✓ The two-pointer approach efficiently calculates trapped water by moving inward from both ends and using max boundaries.

This insight is hard to see from code alone because it requires understanding why the smaller height pointer moves and how max boundaries limit trapped water.

✓ Trapped water at each position depends on the difference between the current height and the max height seen so far on that side.

Visualizing the max heights and pointer movements clarifies how water accumulates only where bars are lower than these boundaries.

✓ Pointer movement decisions are based on comparing heights at pointers, ensuring the algorithm processes the limiting side first.

The trace shows concrete examples of when and why the left or right pointer moves, which is subtle in code but clear visually.

Practice

1. Consider the following Python code implementing the optimal Alien Dictionary solution. Given the input words = ["wrt", "wrf", "er", "ett", "rftt"], what is the final output string returned by the function?

easy

A. "wrtef"

B. "wert"

C. "wertf"

D. "wretf"

Solution

1. Step 1: Build graph edges from adjacent words

   Edges: w->e (from "wrt" and "wrf"), e->r ("wrf" and "er"), r->t ("er" and "ett"), t->f ("ett" and "rftt")

2. Step 2: Perform topological sort using Kahn's algorithm

   Start with nodes with zero in-degree: w; order: w -> e -> r -> t -> f

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output "wertf" matches topological order from graph [OK]

Hint: Trace edges and zero in-degree queue carefully [OK]

Common Mistakes:

• Off-by-one in queue processing
• Ignoring some edges
• Returning partial order

2. You are given an array of balloons, each with a number representing coins. When you burst a balloon, you gain coins equal to the product of the balloon's number and its adjacent balloons' numbers. After bursting, the balloon disappears, and the neighbors become adjacent. Which algorithmic approach guarantees finding the maximum coins you can collect by bursting all balloons in an optimal order?

easy

A. A greedy algorithm that always bursts the balloon with the smallest number first

B. Sorting balloons and bursting them in ascending order to maximize adjacent products

C. A simple depth-first search without memoization to explore all bursting sequences

D. Dynamic programming that considers all subproblems of bursting balloons between indices and uses bottom-up tabulation

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing coins by choosing the order of bursting balloons, where each burst depends on neighbors that change dynamically.

2. Step 2: Identify algorithmic pattern

   Greedy or sorting approaches fail because the optimal choice depends on future bursts. DFS without memoization is exponential and inefficient. Dynamic programming with bottom-up tabulation systematically solves overlapping subproblems and ensures optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP solves all subproblems optimally [OK]

Hint: Optimal order depends on future bursts, so DP is needed [OK]

Common Mistakes:

• Assuming greedy bursting works
• Ignoring overlapping subproblems
• Not using memoization

3. What is the time complexity of the optimized sliding window algorithm for the Minimum Window Substring problem, assuming the input strings have lengths n and m respectively, and the character set is fixed ASCII (size 128)?

medium

A. O(n * m) because for each character in s, we check all characters in t

B. O(n) because each character in s is visited at most twice by the two pointers

C. O(n log n) due to sorting or balanced tree operations on window counts

D. O(n + m) because we initialize frequency arrays and scan s once

Solution

1. Step 1: Analyze outer and inner loops

   The right pointer moves from 0 to n-1 once, and the left pointer moves forward only when conditions are met, also at most n times.

2. Step 2: Confirm linear time complexity

   Each character is processed at most twice (once when right pointer moves forward, once when left pointer moves forward), so total time is O(n). Frequency arrays are fixed size (128), so operations are O(1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer sliding window with fixed frequency arrays is O(n) time [OK]

Hint: Two pointers each traverse string once -> O(n) time [OK]

Common Mistakes:

• Confusing with brute force O(n*m)
• Assuming sorting or complex data structures involved

4. What is the time complexity of the optimal algorithm that sorts envelopes by width ascending and height descending, then finds the Longest Increasing Subsequence (LIS) on heights using binary search?

medium

A. O(n) since LIS can be done in linear time after sorting

B. O(n²) due to nested loops in LIS calculation

C. O(n log n) for sorting plus O(n²) for LIS, total O(n²)

D. O(n log n) because sorting is O(n log n) and LIS with binary search is O(n log n)

Solution

1. Step 1: Analyze sorting complexity

   Sorting envelopes by width and height takes O(n log n).

2. Step 2: Analyze LIS with binary search

   LIS with binary search runs in O(n log n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Overall complexity is dominated by O(n log n) sorting and LIS [OK]

Hint: Sorting + LIS with binary search -> O(n log n) [OK]

Common Mistakes:

• Assuming LIS is always O(n²)
• Ignoring binary search optimization in LIS
• Confusing sorting and LIS complexities

5. What is the time complexity of the divide and conquer approach to the Skyline Problem when given n buildings, and why might a common misconception about the complexity be incorrect?

medium

A. O(n log n) because the problem is divided into halves and merged efficiently

B. O(n log n) time but O(n²) space due to storing all intermediate skylines

C. O(n log n) but with additional O(n) space overhead for recursion stack making it O(n log n) space

D. O(n²) because each merge step compares all points in both skylines

Solution

1. Step 1: Identify divide and conquer structure

   The buildings are split into halves recursively, leading to log n levels.

2. Step 2: Analyze merge cost per level

   Each merge step processes all points in the two skylines combined, which sums to O(n) per level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Divide and conquer with linear merge per level -> O(n log n) time [OK]

Hint: Divide and conquer merges cost O(n) per level over log n levels [OK]

Common Mistakes:

• Assuming merge is O(n²) due to nested loops
• Confusing recursion stack space with time complexity
• Thinking space grows quadratically due to intermediate skylines