Trapping Rain Water Problem in DSA Go - Execution Trace

Concept Flow - Trapping Rain Water Problem

Start with height array

↓

Find max height to left for each bar

↓

Find max height to right for each bar

↓

Calculate trapped water at each bar: min(left_max, right_max) - height

↓

Sum all trapped water amounts

↓

Return total trapped water

The flow finds the highest bar on left and right for each position, then calculates trapped water by the difference, summing all.

Execution Sample

DSA Go

heights := []int{0,1,0,2,1,0,1,3,2,1,2,1}
leftMax := make([]int, len(heights))
rightMax := make([]int, len(heights))
// Calculate leftMax and rightMax arrays
// Calculate trapped water
return totalWater

This code calculates trapped water by precomputing max heights on left and right, then sums trapped water at each bar.

Execution Table

Step	Operation	Index	leftMax	rightMax	Water Trapped at Index	Total Water	Visual State
1	Initialize leftMax[0]	0	0	-	0	0	[0]
2	Calculate leftMax[1]	1	1	-	0	0	[0,1]
3	Calculate leftMax[2]	2	1	-	1	1	[0,1,1]
4	Calculate leftMax[3]	3	2	-	0	1	[0,1,1,2]
5	Calculate leftMax[4]	4	2	-	0	1	[0,1,1,2,2]
6	Calculate leftMax[5]	5	2	-	0	1	[0,1,1,2,2,2]
7	Calculate leftMax[6]	6	2	-	0	1	[0,1,1,2,2,2,2]
8	Calculate leftMax[7]	7	3	-	0	1	[0,1,1,2,2,2,2,3]
9	Calculate leftMax[8]	8	3	-	0	1	[0,1,1,2,2,2,2,3,3]
10	Calculate leftMax[9]	9	3	-	0	1	[0,1,1,2,2,2,2,3,3,3]
11	Calculate leftMax[10]	10	3	-	0	1	[0,1,1,2,2,2,2,3,3,3,3]
12	Calculate leftMax[11]	11	3	-	0	1	[0,1,1,2,2,2,2,3,3,3,3,3]
13	Initialize rightMax[last]	11	-	1	0	1	[...], rightMax[11]=1
14	Calculate rightMax[10]	10	-	2	0	1	rightMax updated
15	Calculate rightMax[9]	9	-	2	1	2	rightMax updated
16	Calculate rightMax[8]	8	-	3	1	3	rightMax updated
17	Calculate rightMax[7]	7	-	3	0	3	rightMax updated
18	Calculate rightMax[6]	6	-	3	1	4	rightMax updated
19	Calculate rightMax[5]	5	-	3	2	6	rightMax updated
20	Calculate rightMax[4]	4	-	3	1	7	rightMax updated
21	Calculate rightMax[3]	3	-	3	0	7	rightMax updated
22	Calculate rightMax[2]	2	-	3	1	8	rightMax updated
23	Calculate rightMax[1]	1	-	3	0	8	rightMax updated
24	Calculate rightMax[0]	0	-	3	0	8	rightMax updated
25	Calculate water trapped at index 2	2	1	3	1	1	Water at 2 = min(1,3)-0=1
26	Calculate water trapped at index 4	4	2	3	1	2	Water at 4 = min(2,3)-1=1
27	Calculate water trapped at index 5	5	2	3	2	4	Water at 5 = min(2,3)-0=2
28	Calculate water trapped at index 6	6	2	3	1	5	Water at 6 = min(2,3)-1=1
29	Calculate water trapped at index 9	9	3	2	1	6	Water at 9 = min(3,2)-1=1
30	Calculate water trapped at index 11	11	3	1	0	6	Water at 11 = min(3,1)-1=0
31	Sum all trapped water	-	-	-	-	6	Total trapped water = 6
32	End	-	-	-	-	6	No more bars to process

💡 All bars processed, total trapped water calculated as 6

Variable Tracker

Variable	Start	After Step 12	After Step 24	After Step 31
leftMax	[0 0 0 0 0 0 0 0 0 0 0 0]	[0 1 1 2 2 2 2 3 3 3 3 3]	[0 1 1 2 2 2 2 3 3 3 3 3]	[0 1 1 2 2 2 2 3 3 3 3 3]
rightMax	[0 0 0 0 0 0 0 0 0 0 0 0]	[0 0 0 0 0 0 0 0 0 0 0 1]	[3 3 3 3 3 3 3 3 3 2 2 1]	[3 3 3 3 3 3 3 3 3 2 2 1]
waterTrapped	0	0	0	6

Key Moments - 3 Insights

Why do we need both leftMax and rightMax arrays?

Because trapped water depends on the minimum of the tallest bars on both sides. leftMax and rightMax arrays store these values for each bar, as shown in steps 2-12 and 13-24.

Why do we subtract the height from min(leftMax, rightMax) to get trapped water?

Because water can only fill up to the shorter of the two tallest bars on either side minus the current bar's height. This is calculated in steps 25-30.

Why is the total trapped water 6 and not more?

Because only positions where min(leftMax, rightMax) is greater than the height trap water. Summing these differences at steps 25-30 gives total 6, confirmed at step 31.

Visual Quiz - 3 Questions

Look at the execution table at step 10, what is the value of leftMax[9]?

A 3

B 2

C 1

D 0

💡 Hint

Check the leftMax column at step 10 in the execution_table.

At which step does the rightMax array get fully calculated?

A Step 12

B Step 24

C Step 31

D Step 18

💡 Hint

Look at the rightMax column updates in the execution_table; full calculation ends at step 24.

If the height at index 5 changed from 0 to 2, how would water trapped at index 5 change?

A Increase

B Decrease

C Stay the same

D Become zero

💡 Hint

Water trapped is min(leftMax, rightMax) - height; increasing height reduces trapped water, see steps 27 and 31.

Concept Snapshot

Trapping Rain Water Problem:
- For each bar, find max height to left and right
- Water trapped = min(leftMax, rightMax) - height
- Sum trapped water for all bars
- Use arrays leftMax and rightMax for O(n) solution
- Total trapped water is sum of positive differences

Full Transcript

The Trapping Rain Water problem calculates how much water can be trapped between bars of different heights. We first find the maximum height to the left of each bar and store it in leftMax array. Then, we find the maximum height to the right of each bar and store it in rightMax array. For each bar, the water trapped is the minimum of leftMax and rightMax minus the bar's height. We sum these values for all bars to get the total trapped water. The execution table shows step-by-step how leftMax and rightMax arrays are built, how water trapped at each index is calculated, and how the total is summed. The variable tracker shows the state of these arrays and the water trapped variable at key steps. Key moments clarify why both arrays are needed, why subtraction is done, and why the total is 6. The visual quiz tests understanding of array values at specific steps and effects of height changes.

Practice

1. What does the Trapping Rain Water problem ask you to find given an array of heights?

easy

A. The minimum height of the bars

B. The maximum height of the bars

C. The total amount of water that can be trapped between the bars after raining

D. The number of bars in the array

Solution

1. Step 1: Understand the problem context

   The problem gives an array representing heights of bars and asks how much water can be trapped between them after rain.

2. Step 2: Identify the goal

   The goal is to calculate the total volume of trapped water, not just heights or counts.

3. Final Answer:

   The total amount of water trapped between bars -> Option C

4. Quick Check:

   Trapping Rain Water = Total trapped water [OK]

Hint: Think of bars as walls holding water in gaps [OK]

Common Mistakes:

• Confusing trapped water with bar heights
• Counting bars instead of water volume
• Ignoring gaps between bars

2. Which of the following Go code snippets correctly initializes an integer slice to represent bar heights for the Trapping Rain Water problem?

easy

A. heights := new int[6]{4, 2, 0, 3, 2, 5}

B. heights := int[]{4, 2, 0, 3, 2, 5}

C. heights := [6]int{4, 2, 0, 3, 2, 5}

D. heights := []int{4, 2, 0, 3, 2, 5}

Solution

1. Step 1: Recall Go slice initialization syntax

   In Go, slices are initialized with []int{values}, arrays with [size]int{values}.

2. Step 2: Identify correct slice syntax

   heights := []int{4, 2, 0, 3, 2, 5} uses []int{...} which is correct for a slice. heights := [6]int{4, 2, 0, 3, 2, 5} is an array, also valid but less flexible.

3. Final Answer:

   heights := []int{4, 2, 0, 3, 2, 5} -> Option D

4. Quick Check:

   Slice syntax = []int{...} [OK]

Hint: Use []int{} for slices, [n]int{} for arrays [OK]

Common Mistakes:

• Using int[] like in other languages
• Trying to use new keyword for slices
• Confusing arrays and slices syntax

3. What is the output of the following Go code snippet that calculates trapped rain water?

package main
import "fmt"
func trap(height []int) int {
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    water := 0
    for left < right {
        if height[left] < height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                water += leftMax - height[left]
            }
            left++
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                water += rightMax - height[right]
            }
            right--
        }
    }
    return water
}
func main() {
    fmt.Println(trap([]int{0,1,0,2,1,0,1,3,2,1,2,1}))
}

medium

A. 6

B. 5

C. 7

D. 8

Solution

1. Step 1: Understand two-pointer approach

   The code uses two pointers moving inward, tracking max heights on left and right to calculate trapped water.

2. Step 2: Trace the example input

   For input [0,1,0,2,1,0,1,3,2,1,2,1], the trapped water calculated by this method is 6 units.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Two-pointer trap water = 6 [OK]

Hint: Use two pointers and track max heights from both ends [OK]

Common Mistakes:

• Not updating max heights correctly
• Adding negative water amounts
• Confusing left and right pointer moves

4. Identify the bug in the following Go code for trapping rain water and select the correct fix:

func trap(height []int) int {
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    water := 0
    for left <= right {
        if height[left] < height[right] {
            if height[left] > leftMax {
                leftMax = height[left]
            } else {
                water += leftMax - height[left]
            }
            left++
        } else {
            if height[right] > rightMax {
                rightMax = height[right]
            } else {
                water += rightMax - height[right]
            }
            right--
        }
    }
    return water
}

medium

A. Change '>' to '>=' in max height comparisons

B. Change loop condition to 'left < right' instead of 'left <= right'

C. Initialize water to 1 instead of 0

D. Swap left and right pointer initial values

Solution

1. Step 1: Analyze loop condition impact

   The loop uses 'left <= right', which causes double counting when left == right.

2. Step 2: Fix loop condition

   Changing to 'left < right' prevents overlap and corrects water calculation.

3. Final Answer:

   Change loop condition to 'left < right' instead of 'left <= right' -> Option B

4. Quick Check:

   Loop condition fix = 'left < right' [OK]

Hint: Use strict less than in two-pointer loops to avoid overlap [OK]

Common Mistakes:

• Using <= causes double counting
• Changing comparison operators incorrectly
• Incorrect pointer initialization

5. Given the heights array [5, 2, 1, 2, 1, 5], what is the total trapped rain water? Use the two-pointer approach to solve.

hard

A. 10

B. 12

C. 8

D. 14

Solution

1. Step 1: Initialize pointers and max heights

   left=0, right=5, leftMax=0, rightMax=0, water=0.

2. Step 2: Move pointers inward calculating trapped water

   - left=0 (height=5) >= leftMax(0), leftMax=5, left++ - left=1 (2) < right=5 (5), height[left]

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Two-pointer sum water = 10 [OK]

Hint: Sum min(leftMax, rightMax) - height at each step [OK]

Common Mistakes:

• Adding water twice for same positions
• Not updating max heights correctly
• Stopping loop too early