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. You are given an integer array and a target value. The task is to count the number of triplets in the array such that the sum of the triplet is less than the target. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use three nested loops to check all triplets and count those with sum less than target.

B. Sort the array, then for each element use two pointers to find pairs that form triplets with sum less than target.

C. Use dynamic programming to store counts of sums and build up to triplets.

D. Use a greedy approach by always picking the smallest elements first to form triplets.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting triplets with sum less than a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach that reduces complexity

   Sorting and using two pointers allows scanning pairs efficiently for each fixed element, reducing complexity from O(n^3) to O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + two pointers is a classic pattern for 3Sum variants [OK]

Hint: Sorting + two pointers reduces triple loops to quadratic [OK]

Common Mistakes:

• Assuming brute force is optimal
• Thinking DP applies directly here
• Believing greedy always works for sum constraints

2. Consider the following code snippet for removing duplicates from a sorted array:

def remove_duplicates(nums):
    if len(nums) == 0:
        return 0
    uniqueIndex = 0
    for currentIndex in range(1, len(nums)):
        if nums[currentIndex] != nums[uniqueIndex]:
            uniqueIndex += 1
            nums[uniqueIndex] = nums[currentIndex]
    return uniqueIndex + 1

arr = [1,1,2]
length = remove_duplicates(arr)
print(length)

What is the output of the print statement?

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Trace uniqueIndex and currentIndex

   Start uniqueIndex=0, currentIndex=1: nums[1]=1 equals nums[0]=1, no increment. currentIndex=2: nums[2]=2 != nums[0]=1, increment uniqueIndex to 1, set nums[1]=2.

2. Step 2: Return value

   uniqueIndex is 1, so return 1+1=2, indicating two unique elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected unique count for input [1,1,2] [OK]

Hint: Unique count equals last uniqueIndex + 1 [OK]

Common Mistakes:

• Returning uniqueIndex instead of uniqueIndex + 1
• Off-by-one errors in loop

3. What is the time complexity of the optimal 3Sum Closest algorithm that sorts the array and uses two pointers to find the closest sum?

medium

A. O(n³) because it checks all triplets

B. O(n²) because it fixes one element and uses two pointers for the other two

C. O(n log n) due to sorting and linear scan

D. O(n² log n) because sorting and binary searching pairs

Solution

1. Step 1: Identify sorting cost

   Sorting takes O(n log n) time.

2. Step 2: Analyze nested loops

   Outer loop runs O(n) times; inner two-pointer scan runs O(n) total per outer iteration -> O(n²).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + two-pointer scanning yields O(n²) total [OK]

Hint: Two pointers inside one loop -> O(n²) time [OK]

Common Mistakes:

• Confusing brute force O(n³) with optimal
• Ignoring sorting cost
• Assuming binary search inside loop

4. The following code attempts to move zeroes to the end of the array in-place:

def moveZeroes(nums):
    lastNonZeroFoundAt = 0
    for num in nums:
        if num != 0:
            nums[lastNonZeroFoundAt] = num
            lastNonZeroFoundAt += 1
    # Bug introduced here
    for i in range(lastNonZeroFoundAt, len(nums)):
        nums[i] = nums[i]

What is the bug in this code?

medium

A. The variable lastNonZeroFoundAt is incremented incorrectly.

B. The first loop does not correctly identify non-zero elements.

C. The second loop does not fill zeroes after lastNonZeroFoundAt, leaving old values intact.

D. The assignment inside the first loop overwrites zeroes incorrectly.

Solution

1. Step 1: Analyze second loop behavior

   The second loop assigns nums[i] = nums[i], which does nothing and fails to fill zeroes.

2. Step 2: Identify correct fix

   It should assign nums[i] = 0 to move zeroes to the end properly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Zeroes remain unfilled, causing incorrect output [OK]

Hint: Second loop must fill zeroes, not copy existing values [OK]

Common Mistakes:

• Forgetting to fill zeroes after moving non-zero elements
• Misunderstanding loop purpose

5. If the problem changes so that the same element can be used multiple times to reach the target sum (i.e., elements can be reused), which approach correctly solves the problem?

hard

A. Use the two pointers approach moving inward, but allow pointers to stay if sum < target to reuse elements.

B. Use a modified binary search that allows searching from the current index (not i+1) to reuse elements.

C. Use a dynamic programming approach to find combinations allowing repeated elements.

D. Use the brute force nested loops but break early when sum exceeds target.

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means pairs can include the same element multiple times, which breaks two-pointer and binary search assumptions.

2. Step 2: Identify suitable approach

   Dynamic programming can handle combinations with repeated elements efficiently, unlike two pointers or binary search.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP handles repeated elements and target sums correctly [OK]

Hint: Reuse -> DP for combinations, not two pointers or binary search [OK]

Common Mistakes:

• Trying to reuse pointers incorrectly
• Modifying binary search without correctness
• Assuming brute force is efficient