Trapping Rain Water Using Stack in DSA Go - Time & Space Complexity

Time Complexity: Trapping Rain Water Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time needed to calculate trapped rain water changes as the input size grows.

Specifically, how the stack-based method handles the input heights affects the total steps taken.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func trap(height []int) int {
    stack := []int{}
    water := 0
    for i := 0; i < len(height); i++ {
        for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                break
            }
            distance := i - stack[len(stack)-1] - 1
            boundedHeight := min(height[i], height[stack[len(stack)-1]]) - height[top]
            water += distance * boundedHeight
        }
        stack = append(stack, i)
    }
    return water
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

This code calculates how much rainwater can be trapped between bars using a stack to track boundaries.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop runs once for each bar in the height array.
• Inner loop: The inner while-loop pops bars from the stack when the current bar is taller.
• How many times: Each bar is pushed and popped at most once, so total stack operations are proportional to the number of bars.

How Execution Grows With Input

As the number of bars increases, the total steps grow roughly in a straight line.

Input Size (n)	Approx. Operations
10	About 20 stack operations (push + pop combined)
100	About 200 stack operations
1000	About 2000 stack operations

Pattern observation: The operations increase linearly with input size because each bar is processed a limited number of times.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute trapped water grows directly in proportion to the number of bars.

Common Mistake

[X] Wrong: "Because there is a nested loop, the time complexity must be O(n²)."

[OK] Correct: The inner loop does not run fully for every outer loop iteration; each bar is pushed and popped only once, so total operations stay linear.

Interview Connect

Understanding this stack approach shows you can use clever data structures to reduce repeated work, a skill valued in problem solving.

Self-Check

"What if we replaced the stack with a simple nested loop checking all pairs? How would the time complexity change?"

Practice

1. What is the main purpose of using a stack in the Trapping Rain Water Using Stack algorithm?

easy

A. To keep track of the indices of bars to calculate trapped water

B. To store the heights of the bars directly

C. To sort the bars in ascending order

D. To reverse the array of bar heights

Solution

1. Step 1: Understand the role of stack

   The stack stores indices of bars, not heights, to help find boundaries for trapped water.

2. Step 2: Use indices to calculate trapped water

   By using indices, we can calculate width and height of trapped water between bars.

3. Final Answer:

   To keep track of the indices of bars to calculate trapped water -> Option A

4. Quick Check:

   Stack stores indices, not heights [OK]

Hint: Stack stores indices to find water boundaries quickly [OK]

Common Mistakes:

• Thinking stack stores heights instead of indices
• Assuming stack sorts bars
• Using stack to reverse array

2. Which of the following Go code snippets correctly declares an empty stack to be used for trapping rain water calculation?

easy

A. stack := []string{}

B. stack := make(map[int]int)

C. var stack []int

D. var stack int

Solution

1. Step 1: Identify correct stack type

   Stack should be a slice of integers to store indices, so var stack []int is correct.

2. Step 2: Check other options

   stack := make(map[int]int) uses a map, not a stack. stack := []string{} uses string slice, wrong type. var stack int is a single int, not a stack.

3. Final Answer:

   var stack []int -> Option C

4. Quick Check:

   Stack as int slice = var stack []int [OK]

Hint: Use slice of int for stack of indices in Go [OK]

Common Mistakes:

• Using map instead of slice for stack
• Using wrong data type like string
• Declaring stack as single int variable

3. What is the output of the following Go code snippet that uses stack to calculate trapped rain water?

heights := []int{0,1,0,2,1,0,1,3,2,1,2,1}
stack := []int{}
water := 0
for i := 0; i < len(heights); i++ {
    for len(stack) > 0 && heights[i] >= heights[stack[len(stack)-1]] {
        top := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if len(stack) == 0 {
            break
        }
        distance := i - stack[len(stack)-1] - 1
        boundedHeight := min(heights[i], heights[stack[len(stack)-1]]) - heights[top]
        water += distance * boundedHeight
    }
    stack = append(stack, i)
}
fmt.Println(water)

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

medium

A. 8

B. 5

C. 7

D. 6

Solution

1. Step 1: Trace the stack and water calculation

   The code implements the standard stack-based trapping rain water algorithm on the given heights array.

2. Step 2: Calculate trapped water for given input

   For input {0,1,0,2,1,0,1,3,2,1,2,1}, trapped water is 6 units.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Standard example input yields 6 units trapped water [OK]

Hint: Use known example array for quick trapped water = 6 [OK]

Common Mistakes:

• Miscounting trapped water units
• Ignoring stack empty check
• Wrong min height calculation

4. Identify the bug in the following Go code snippet for trapping rain water using stack:

heights := []int{4,2,0,3,2,5}
stack := []int{}
water := 0
for i := 0; i < len(heights); i++ {
    for len(stack) > 0 && heights[i] > heights[stack[len(stack)-1]] {
        top := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if len(stack) == 0 {
            break
        }
        distance := i - stack[len(stack)-1] - 1
        boundedHeight := min(heights[i], heights[stack[len(stack)-1]]) - heights[top]
        water += distance * boundedHeight
    }
    stack = append(stack, i)
}
fmt.Println(water)

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

What is the bug?

medium

A. Using '>' instead of '>=' in the inner loop condition

B. Not checking if stack is empty before popping

C. Incorrect calculation of distance between bars

D. Using min function incorrectly

Solution

1. Step 1: Analyze inner loop condition

   The condition uses '>' but it should be '>=' to correctly handle equal height bars.

2. Step 2: Effect of wrong condition

   Using '>' skips popping when heights are equal, causing incorrect trapped water calculation.

3. Final Answer:

   Using '>' instead of '>=' in the inner loop condition -> Option A

4. Quick Check:

   Use '>=' to handle equal heights correctly [OK]

Hint: Use '>=' in condition to pop equal or smaller bars [OK]

Common Mistakes:

• Using '>' instead of '>=' causing missed pops
• Not checking stack empty before pop (though code does)
• Miscomputing distance or bounded height

5. Given the heights array []int{3, 0, 2, 0, 4}, how much water will be trapped using the stack-based algorithm? Also, explain why the stack helps in this case.

hard

A. 6 units

B. 7 units

C. 5 units

D. 4 units

Solution

1. Step 1: Calculate trapped water manually

   Water at pos1: 3 units, pos2: 1 unit, pos3: 3 units. Total trapped water = 7 units.

2. Step 2: Explain stack role

   The stack stores indices of bars to find left and right boundaries for water trapping, allowing calculation of width and height of trapped water efficiently.

3. Final Answer:

   7 units -> Option B

4. Quick Check:

   Stack trace or min(leftmax,rightmax)-h sum = 7 units [OK]

Hint: Sum trapped water between boundaries using stack indices [OK]

Common Mistakes:

• Miscounting trapped water between bars
• Not understanding stack helps find boundaries
• Ignoring zero height bars in calculation