Trapping Rain Water Problem in DSA C - 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

↓

Sum all trapped water

↓

Return total trapped water

The flow shows how we find max heights on left and right sides for each bar, then calculate trapped water by comparing bar height with these max heights.

Execution Sample

DSA C

int trap(int* height, int heightSize) {
  int leftMax[heightSize], rightMax[heightSize];
  int water = 0;
  // compute leftMax and rightMax arrays
  // calculate trapped water
  return water;
}

This code calculates how much water can be trapped after raining given an array of bar heights.

Execution Table

Step	Operation	Index	LeftMax Array	RightMax Array	Water Trapped at Index	Total Water	Visual State
1	Initialize leftMax[0]	0	[2, _, _, _, _]	[_, _, _, _, _]	0	0	2 _ _ _ _
2	Compute leftMax[1]	1	[2, 2, _, _, _]	[_, _, _, _, _]	0	0	2 1 _ _ _
3	Compute leftMax[2]	2	[2, 2, 3, _, _]	[_, _, _, _, _]	0	0	2 1 3 _ _
4	Compute leftMax[3]	3	[2, 2, 3, 3, _]	[_, _, _, _, _]	0	0	2 1 3 2 _
5	Compute leftMax[4]	4	[2, 2, 3, 3, 4]	[_, _, _, _, _]	0	0	2 1 3 2 4
6	Initialize rightMax[4]	4	[2, 2, 3, 3, 4]	[_, _, _, _, 4]	0	0	2 1 3 2 4
7	Compute rightMax[3]	3	[2, 2, 3, 3, 4]	[_, _, _, 4, 4]	0	0	2 1 3 2 4
8	Compute rightMax[2]	2	[2, 2, 3, 3, 4]	[_, _, 4, 4, 4]	0	0	2 1 3 2 4
9	Compute rightMax[1]	1	[2, 2, 3, 3, 4]	[_, 4, 4, 4, 4]	0	0	2 1 3 2 4
10	Compute rightMax[0]	0	[2, 2, 3, 3, 4]	[4, 4, 4, 4, 4]	0	0	2 1 3 2 4
11	Calculate water at index 0	0	[2, 2, 3, 3, 4]	[4, 4, 4, 4, 4]	0	0	2 1 3 2 4
12	Calculate water at index 1	1	[2, 2, 3, 3, 4]	[4, 4, 4, 4, 4]	1	1	2 1 3 2 4
13	Calculate water at index 2	2	[2, 2, 3, 3, 4]	[4, 4, 4, 4, 4]	0	1	2 1 3 2 4
14	Calculate water at index 3	3	[2, 2, 3, 3, 4]	[4, 4, 4, 4, 4]	1	2	2 1 3 2 4
15	Calculate water at index 4	4	[2, 2, 3, 3, 4]	[4, 4, 4, 4, 4]	0	2	2 1 3 2 4
16	Return total trapped water	-	[2, 2, 3, 3, 4]	[4, 4, 4, 4, 4]	-	2	2 1 3 2 4

💡 All indices processed, total trapped water calculated as 2 units.

Variable Tracker

Variable	Start	After Step 5	After Step 10	After Step 15	Final
leftMax	[_, _, _, _, _]	[2, 2, 3, 3, 4]	[2, 2, 3, 3, 4]	[2, 2, 3, 3, 4]	[2, 2, 3, 3, 4]
rightMax	[_, _, _, _, _]	[_, _, _, _, _]	[4, 4, 4, 4, 4]	[4, 4, 4, 4, 4]	[4, 4, 4, 4, 4]
water	0	0	0	2	2
totalWater	0	0	0	2	2

Key Moments - 3 Insights

Why do we need to find max heights on both left and right sides?

Because water trapped depends on the smaller of the tallest bars on left and right sides. This is shown in steps 2-10 where leftMax and rightMax arrays are built.

Why is water trapped zero at the first and last bars?

At edges, there is no bar on one side to hold water, so trapped water is zero as seen in steps 11 and 16.

How do we calculate water trapped at each index?

Water trapped = min(leftMax[i], rightMax[i]) - height[i]. This is applied in steps 11-15.

Visual Quiz - 3 Questions

Look at the execution table at step 12, what is the water trapped at index 1?

A 1

B 0

C 2

D 3

💡 Hint

Check the 'Water Trapped at Index' column at step 12 in the execution_table.

At which step does the rightMax array get fully computed?

A Step 5

B Step 10

C Step 15

D Step 12

💡 Hint

Look at the 'RightMax Array' column in the execution_table and find when it has no underscores.

If the height at index 3 was increased to 4, how would the total trapped water change?

A It would increase

B It would stay the same

C It would decrease

D It would become zero

💡 Hint

Consider how water trapped depends on min(leftMax, rightMax) - height at each index, check variable_tracker for water values.

Concept Snapshot

Trapping Rain Water Problem:
- Given array of bar heights
- Compute max height to left and right for each bar
- Water trapped at bar = min(leftMax, rightMax) - height
- Sum all trapped water
- Edges trap no water

Full Transcript

The Trapping Rain Water problem calculates how much water can be trapped between bars after raining. We first find the maximum height to the left and right of each bar. Then, for each bar, the water trapped is the smaller of these two max heights minus the bar's own height. We sum these values for all bars to get the total trapped water. The edges trap no water because there is no boundary on one side. This process is shown step-by-step in the execution table, tracking arrays leftMax, rightMax, and water trapped at each index.

Practice

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

easy

A. The minimum height of the bars

B. The maximum height of the bars

C. The number of bars in the array

D. The total amount of water trapped between the bars after raining

Solution

1. Step 1: Understand the problem context

   The problem involves an array representing heights of bars where water can be trapped between them.

2. Step 2: Identify the goal

   The goal is to calculate how much water can be trapped after raining between these bars.

3. Final Answer:

   The total amount of water trapped between the bars after raining -> Option D

4. Quick Check:

   Trapping Rain Water = Total trapped water [OK]

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

Common Mistakes:

• Confusing trapped water with bar heights
• Calculating max or min height instead of trapped water
• Ignoring the space between bars

2. Which of the following C code snippets correctly declares an array to store bar heights for the Trapping Rain Water problem?

easy

A. int heights[] = {4, 2, 0, 3, 2, 5};

B. int heights = {4, 2, 0, 3, 2, 5};

C. int heights[6] = (4, 2, 0, 3, 2, 5);

D. int heights[6] = [4, 2, 0, 3, 2, 5];

Solution

1. Step 1: Check array declaration syntax in C

   Arrays are declared with type, name, and initializer list in braces {}.

2. Step 2: Validate each option

   int heights[] = {4, 2, 0, 3, 2, 5}; uses correct syntax: int heights[] = {4, 2, 0, 3, 2, 5}; Options A, B, D have syntax errors.

3. Final Answer:

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

4. Quick Check:

   Correct C array syntax = int heights[] = {4, 2, 0, 3, 2, 5}; [OK]

Hint: Use braces {} to initialize arrays in C [OK]

Common Mistakes:

• Using parentheses () instead of braces {}
• Missing array size or incorrect initializer syntax
• Using square brackets [] for initialization

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

int heights[] = {3, 0, 2, 0, 4};
int n = 5;
int left_max[5], right_max[5];
int water = 0;

// Calculate left max
left_max[0] = heights[0];
for (int i = 1; i < n; i++) {
    left_max[i] = (heights[i] > left_max[i-1]) ? heights[i] : left_max[i-1];
}

// Calculate right max
right_max[n-1] = heights[n-1];
for (int i = n-2; i >= 0; i--) {
    right_max[i] = (heights[i] > right_max[i+1]) ? heights[i] : right_max[i+1];
}

// Calculate trapped water
for (int i = 0; i < n; i++) {
    water += (left_max[i] < right_max[i] ? left_max[i] : right_max[i]) - heights[i];
}

printf("%d\n", water);

medium

A. 4

B. 6

C. 7

D. 5

Solution

1. Step 1: Calculate left_max and right_max arrays

   left_max = [3, 3, 3, 3, 4], right_max = [4, 4, 4, 4, 4]

2. Step 2: Calculate trapped water at each index

   Water trapped = sum of min(left_max[i], right_max[i]) - heights[i] = (3-3)+(3-0)+(3-2)+(3-0)+(4-4) = 0+3+1+3+0 = 7

3. Final Answer:

   7 -> Option C

4. Quick Check:

   Sum trapped water = 7 [OK]

Hint: Use left_max and right_max arrays to find trapped water fast [OK]

Common Mistakes:

• Mixing up left_max and right_max arrays
• Forgetting to subtract heights from min of max arrays
• Off-by-one errors in loops

4. Identify the bug in this C code snippet for calculating trapped rain water:

int trap(int* height, int heightSize) {
    int left_max[heightSize];
    int right_max[heightSize];
    int water = 0;

    left_max[0] = height[0];
    for (int i = 1; i < heightSize; i++) {
        left_max[i] = height[i] > left_max[i-1] ? height[i] : left_max[i-1];
    }

    right_max[heightSize-1] = height[heightSize-1];
    for (int i = heightSize-2; i >= 0; i--) {
        right_max[i] = height[i] > right_max[i+1] ? height[i] : right_max[i+1];
    }

    for (int i = 0; i < heightSize; i++) {
        water += (left_max[i] < right_max[i] ? left_max[i] : right_max[i]) - height[i];
    }

    return water;
}

medium

A. Incorrect comparison operator in left_max calculation

B. Using variable length arrays (VLA) which may not be supported

C. Wrong loop range in right_max calculation

D. Missing initialization of water variable

Solution

1. Step 1: Analyze array declarations

   The code uses int left_max[heightSize]; and int right_max[heightSize]; which are variable length arrays (VLA).

2. Step 2: Understand VLA support in C

   VLAs are optional in C11 and may not be supported by all compilers, causing portability issues or errors.

3. Final Answer:

   Using variable length arrays (VLA) which may not be supported -> Option B

4. Quick Check:

   VLAs may cause errors = Using variable length arrays (VLA) which may not be supported [OK]

Hint: Avoid VLAs; use dynamic memory or fixed size arrays [OK]

Common Mistakes:

• Assuming VLAs always work in all C compilers
• Ignoring compiler warnings about VLAs
• Confusing VLA issue with logic errors

5. Given the heights array {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}, what is the total trapped rain water using the two-pointer approach in C?

hard

A. 6

B. 5

C. 7

D. 8

Solution

1. Step 1: Understand two-pointer approach

   Use two pointers left and right starting at ends, track left_max and right_max, move pointers inward calculating trapped water.

2. Step 2: Dry run the array

   Heights: [0,1,0,2,1,0,1,3,2,1,2,1] Water trapped = 6 units after calculating min(left_max, right_max) - height at each step.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Two-pointer trapped water = 6 [OK]

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

Common Mistakes:

• Not updating left_max and right_max correctly
• Moving pointers incorrectly causing missed water
• Confusing two-pointer with prefix arrays method