Trapping Rain Water Problem in DSA Go - Deep Dive

Overview - Trapping Rain Water Problem

What is it?

The Trapping Rain Water Problem asks how much water can be trapped between bars of different heights after it rains. Imagine each bar as a wall that can hold water between itself and neighboring walls. The goal is to find the total amount of water trapped without spilling. This problem helps us understand how to use arrays and pointers to solve real-world space problems.

Why it matters

Without this concept, we would struggle to solve problems involving space optimization and fluid containment in programming. It teaches how to think about boundaries and limits in data, which is useful in many fields like game design, architecture, and even data compression. Without it, we might waste resources or fail to model real-world scenarios accurately.

Where it fits

Before this, learners should understand arrays and basic loops. After this, they can explore two-pointer techniques, dynamic programming, and more complex space optimization problems.

Mental Model

Core Idea

Water trapped above a bar depends on the tallest bars to its left and right, and the trapped amount is the minimum of these heights minus the bar's own height.

Think of it like...

Imagine a row of uneven buckets placed side by side. When it rains, water fills the gaps between buckets up to the height of the shortest bucket on either side, but never overflows the buckets themselves.

Index:  0   1   2   3   4   5   6
Height: █   █       █       █   █
        █   █   █   █   █   █   █
Water:      ~~~~     ~~~~       

Legend:
█ = bar height
~ = trapped water between bars

Build-Up - 6 Steps

1

Foundation

Understanding the Problem Setup

Concept: Introduce the problem scenario and what trapping rain water means in terms of bar heights.

We have an array where each number represents the height of a vertical bar. When it rains, water can collect between these bars if there are taller bars on both sides. Our task is to find how much water is trapped in total after the rain stops.

Result

Clear mental picture of bars and water trapped between them.

Understanding the physical setup helps connect the problem to real-world intuition, making the abstract array easier to grasp.

2

Foundation

Basic Array Traversal and Height Comparison

Concept: Learn to scan the array and compare bar heights to find potential water traps.

We look at each bar and check the tallest bar on its left and right. The water above this bar is limited by the shorter of these two tallest bars minus the bar's own height. If this difference is positive, it means water is trapped here.

Result

Ability to calculate trapped water at a single position.

Breaking down the problem to a single bar's trapped water simplifies the overall challenge.

3

Intermediate

Precomputing Left and Right Max Arrays

🤔Before reading on: Do you think we can find trapped water without checking all bars repeatedly? Commit to yes or no.

Concept: Use extra arrays to store the tallest bar to the left and right of each position to avoid repeated scanning.

Create two arrays: leftMax and rightMax. leftMax[i] stores the tallest bar from the start up to i. rightMax[i] stores the tallest bar from the end up to i. Then, for each bar, trapped water = min(leftMax[i], rightMax[i]) - height[i].

Result

Efficient calculation of trapped water with O(n) time and O(n) space.

Precomputing saves time by avoiding repeated work, a key optimization technique.

4

Intermediate

Two-Pointer Technique for Space Optimization

🤔Before reading on: Can we find trapped water without extra arrays? Commit to yes or no.

Concept: Use two pointers moving inward from both ends to calculate trapped water using constant space.

Initialize two pointers at the start and end of the array. Keep track of leftMax and rightMax as you move pointers inward. At each step, move the pointer with the smaller height, calculate trapped water if any, and update max heights. This avoids extra arrays and uses O(1) space.

Result

Same result as before but with less memory used.

Two-pointer approach cleverly uses problem properties to optimize space without losing clarity.

5

Advanced

Implementing the Two-Pointer Algorithm in Go

🤔Before reading on: Do you think the two-pointer method is harder or easier to implement than precomputing arrays? Commit to your answer.

Concept: Write complete Go code using two pointers to solve the problem efficiently.

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

Result

6

Implementing the algorithm solidifies understanding and shows how theory translates to working code.

6

Expert

Analyzing Edge Cases and Performance

🤔Before reading on: Do you think the algorithm handles empty or uniform height arrays correctly? Commit to yes or no.

Concept: Explore how the algorithm behaves with special inputs and its time and space complexity.

Edge cases include empty arrays, arrays with all bars of the same height, or strictly increasing/decreasing heights. The two-pointer method gracefully handles these by never trapping water when no boundaries exist. Time complexity is O(n) because each pointer moves once. Space complexity is O(1) since no extra arrays are used.

Result

Robustness and efficiency confirmed for all input types.

Knowing edge cases and complexity ensures confidence in using the algorithm in real systems.

Under the Hood

The algorithm works by maintaining two pointers and two variables tracking the maximum height seen so far from the left and right. At each step, it moves the pointer with the smaller height inward, updating the max height and calculating trapped water as the difference between the max height and current bar height. This works because trapped water depends on the shorter boundary, and moving from the smaller side guarantees correct calculation without missing any trapped water.

Why designed this way?

Originally, the problem was solved by checking all bars repeatedly, which was slow. Precomputing max arrays improved speed but used extra space. The two-pointer method was designed to optimize both time and space by leveraging the insight that trapped water depends on the smaller boundary. This design balances efficiency and simplicity, making it practical for large inputs.

┌─────────────┐
│ Start:      │
│ left=0      │
│ right=n-1   │
│ leftMax=0   │
│ rightMax=0  │
└─────┬───────┘
      │
      ▼
┌─────────────────────────────┐
│ Compare height[left] and    │
│ height[right]               │
│ If height[left]<height[right]│
│   Update leftMax or add water│
│   Move left pointer right   │
│ Else                       │
│   Update rightMax or add water│
│   Move right pointer left   │
└─────────────┬───────────────┘
              │
              ▼
      ┌─────────────┐
      │ Repeat until│
      │ left >= right│
      └─────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does trapped water depend only on the tallest bar on one side? Commit yes or no.

Common Belief: Trapped water depends only on the tallest bar on the left side.

Reality: Trapped water depends on the shorter of the tallest bars on both left and right sides.

Why it matters: Ignoring the right side boundary leads to overestimating trapped water and incorrect results.

Quick: Can we calculate trapped water by just summing differences between adjacent bars? Commit yes or no.

Common Belief: Summing height differences between adjacent bars gives total trapped water.

Reality: Adjacent differences don't capture trapped water because water can be trapped over multiple bars, not just between neighbors.

Why it matters: This misconception causes undercounting or missing trapped water in valleys spanning multiple bars.

Quick: Does the two-pointer method require extra arrays to work? Commit yes or no.

Common Belief: Two-pointer method needs extra arrays to store max heights.

Reality: Two-pointer method uses variables to track max heights on the fly, avoiding extra arrays.

Why it matters: Believing extra arrays are needed leads to inefficient solutions and missed optimization opportunities.

Expert Zone

1

The two-pointer method relies on the invariant that the pointer at the smaller height side can safely calculate trapped water without missing any, a subtle but crucial insight.

2

In some variations, precomputing max arrays is preferred when multiple queries on the same height array are needed, trading space for query speed.

3

The problem can be extended to 2D grids (trapping rain water II), where the logic becomes more complex and requires priority queues.

When NOT to use

Avoid the two-pointer method when you need to answer multiple queries on the same data quickly; precomputing prefix and suffix max arrays is better. For 2D or irregular shapes, specialized algorithms like BFS with priority queues are required.

Production Patterns

Used in terrain modeling to estimate water accumulation, in game development for realistic water physics, and in interview coding tests to assess problem-solving and optimization skills.

Connections

Two-Pointer Technique

Builds-on

Understanding trapping rain water deepens grasp of two-pointer methods, showing how pointers can be moved based on conditions to optimize space and time.

Dynamic Programming

Related optimization pattern

Precomputing left and right max arrays is a form of dynamic programming, storing intermediate results to avoid repeated work.

Hydrology and Geography

Real-world application

The problem models how water collects in valleys and basins, linking computer algorithms to natural water flow and terrain analysis.

Common Pitfalls

#1 Calculating trapped water using only one side's max height.

Wrong approach:

for i := 0; i < len(height); i++ {
trapped += leftMax[i] - height[i] // ignores right max
}

Correct approach:

for i := 0; i < len(height); i++ {
trapped += min(leftMax[i], rightMax[i]) - height[i]
}

Root cause:

Misunderstanding that water is limited by both sides, not just one.

#2 Using nested loops to find max heights for each bar repeatedly.

Wrong approach:

for i := 0; i < len(height); i++ {
leftMax := max(height[0..i])
rightMax := max(height[i..end])
trapped += min(leftMax, rightMax) - height[i]
}

Correct approach:

Precompute leftMax and rightMax arrays once, then iterate once to calculate trapped water.

Root cause:

Not optimizing repeated work leads to inefficient O(n^2) time.

#3 Moving pointers incorrectly in two-pointer method, causing missed trapped water.

Wrong approach:

if height[left] > height[right] {
left++ // wrong pointer moved
} else {
right--
}

Correct approach:

if height[left] < height[right] {
left++
} else {
right--
}

Root cause:

Confusing which pointer to move based on height comparison breaks the algorithm's logic.

Key Takeaways

Trapped water above a bar depends on the minimum of the tallest bars on its left and right sides minus its own height.

Precomputing max heights on both sides allows efficient calculation but uses extra space.

The two-pointer technique optimizes space by moving pointers inward and updating max heights on the fly.

Edge cases like empty or uniform height arrays are handled naturally by the two-pointer method.

Understanding this problem builds skills in array manipulation, optimization, and real-world modeling.

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