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.