Trapping Rain Water Problem in DSA Java - 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, and water fills the gaps between them. The goal is to find the total amount of water that stays trapped without spilling. This problem helps us understand how to work with arrays and calculate areas efficiently.

Why it matters

Without this concept, we would struggle to solve real-world problems involving water flow, storage, or even data compression where space between elements matters. It teaches us how to think about boundaries and limits in a sequence, which is useful in many fields like civil engineering and computer graphics. Without it, we might waste time with slow or incorrect solutions.

Where it fits

Before this, learners should understand arrays and basic loops. After this, they can explore more complex array problems like sliding windows or dynamic programming. This problem is a stepping stone to mastering efficient space and time optimization techniques.

Mental Model

Core Idea

Water trapped at any position depends on the tallest bars to its left and right, and the trapped water is the difference between the smaller of these two heights and the bar's own height.

Think of it like...

Imagine a row of uneven buckets placed side by side. When you pour water over them, water fills the smaller buckets up to the height of the shortest bucket on either side, but never overflows the tallest bucket walls.

Index:  0   1   2   3   4   5   6   7
Height: [0,  1,  0,  2,  1,  0,  1,  3]

Water:  [0,  0,  1,  0,  1,  2,  1,  0]

Diagram:
  ┌─┐       ┌─┐
  │ │   ┌─┐ │ │
┌─┤ │ ┌─┤ │ │ │
│ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │
0 1 0 2 1 0 1 3

Build-Up - 6 Steps

1

Foundation

Understanding the Problem Setup

Concept: Introduce the problem using a simple array representing bar heights and explain what trapping water means.

Given an array where each element represents the height of a bar, water can be trapped between bars if there are taller bars on both sides. For example, in [0,1,0,2], water can fill the gap at index 2 up to height 1 because bars at index 1 and 3 are taller.

Result

Learners visualize how water fills gaps between bars based on their heights.

Understanding the physical setup helps connect the problem to a real-world scenario, making the abstract array more tangible.

2

Foundation

Brute Force Approach Explanation

Concept: Calculate trapped water at each position by checking the tallest bar on the left and right.

For each bar, find the maximum height to its left and right. The water trapped is the minimum of these two heights minus the bar's height. Sum this for all bars. This requires nested loops: one to find left max, one for right max, for each bar.

Result

Correct but slow solution with O(n^2) time complexity.

This step shows the direct but inefficient way, setting the stage for optimization.

3

Intermediate

Using Precomputed Max Arrays

🤔Before reading on: do you think precomputing max heights on both sides will reduce the time complexity? Commit to yes or no.

Concept: Store the tallest bar to the left and right of each position in separate arrays to avoid repeated scanning.

Create two arrays: leftMax and rightMax. leftMax[i] stores the tallest bar from start to i. rightMax[i] stores the tallest bar from end to i. Then, trapped water at i is min(leftMax[i], rightMax[i]) - height[i]. This reduces time to O(n) but uses extra space.

Result

Efficient O(n) time and O(n) space solution.

Precomputing saves repeated work, showing how extra space can improve speed.

4

Intermediate

Two-Pointer Technique for Optimization

🤔Before reading on: can we solve this problem in one pass without extra arrays? Commit to yes or no.

Concept: Use two pointers moving inward from both ends, tracking max heights on the fly to calculate trapped water in one pass.

Initialize two pointers at start and end. Keep track of leftMax and rightMax. Move the pointer with smaller height inward, update max, and add trapped water if current bar is lower. This uses O(1) space and O(n) time.

Result

Optimal solution with linear time and constant space.

This technique cleverly uses the problem's constraints to avoid extra memory, improving efficiency.

5

Advanced

Implementing Two-Pointer Solution in Java

🤔Before reading on: predict the output for input [4,2,0,3,2,5]. How much water is trapped? Commit to your answer.

Concept: Write clean, runnable Java code using the two-pointer approach to solve the problem.

public class TrappingRainWater { public static int trap(int[] height) { int left = 0, right = height.length - 1; int leftMax = 0, rightMax = 0; int trappedWater = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= leftMax) leftMax = height[left]; else trappedWater += leftMax - height[left]; left++; } else { if (height[right] >= rightMax) rightMax = height[right]; else trappedWater += rightMax - height[right]; right--; } } return trappedWater; } public static void main(String[] args) { int[] height = {4,2,0,3,2,5}; System.out.println(trap(height)); } }

Result

Output: 9

Seeing the full code and output confirms understanding and builds confidence in applying the two-pointer method.

6

Expert

Analyzing Edge Cases and Performance

🤔Before reading on: do you think the two-pointer method handles empty or uniform height arrays correctly? Commit to yes or no.

Concept: Explore how the solution behaves with edge cases and why it remains efficient.

For empty arrays or arrays with no dips, trapped water is zero. The two-pointer method naturally returns zero without extra checks. It also handles large inputs efficiently due to O(n) time and O(1) space. Understanding this helps avoid bugs and optimize real-world usage.

Result

Robust, efficient solution that gracefully handles all input types.

Knowing edge case behavior prevents runtime errors and builds trust in the algorithm's reliability.

Under the Hood

The two-pointer method works by maintaining two pointers at the array ends and moving inward. At each step, it compares the heights at these pointers and moves the smaller one, updating the maximum height seen so far on that side. The trapped water at each position is calculated by subtracting the current height from the known maximum boundary height. This works because water trapping depends on the shorter boundary limiting the water level.

Why designed this way?

The problem was designed to find an efficient way to avoid repeated scanning of the array for max heights. The two-pointer approach was chosen because it leverages the insight that trapped water depends on the smaller boundary, allowing a single pass with constant space. Alternatives like brute force were too slow, and precomputing arrays used extra space, so this method balances speed and memory.

┌───────────────┐
│   Start       │
│ left=0, right=n-1 │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ Compare height[left] and height[right] │
└────────────┬────────────────┘
             │
    ┌────────┴─────────┐
    │                  │
left height < right height  left height >= right height
    │                  │
Move left pointer right   Move right pointer left
Update leftMax and trapped water  Update rightMax and trapped water
    │                  │
    └────────┬─────────┘
             │
             ▼
       Repeat until left >= right

Myth Busters - 4 Common Misconceptions

Quick: Does the trapped water at a position depend only on the tallest bar to its left? Commit to yes or no.

Common Belief: Trapped water depends only on the tallest bar to the left of a position.

Reality: Trapped water depends on the smaller of the tallest bars to the left and right of that position.

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

Quick: Is the brute force method efficient enough for very large arrays? Commit to yes or no.

Common Belief: Brute force is fine for all input sizes since it always works.

Reality: Brute force has O(n^2) time complexity and becomes too slow for large inputs.

Why it matters: Using brute force in production can cause performance bottlenecks and timeouts.

Quick: Can the two-pointer method be applied if the array is not sorted? Commit to yes or no.

Common Belief: The two-pointer method requires the array to be sorted by height.

Reality: The array does not need to be sorted; the method works on any height arrangement.

Why it matters: Misunderstanding this limits the method's applicability and causes unnecessary sorting.

Quick: Does the trapped water volume ever become negative at any position? Commit to yes or no.

Common Belief: Trapped water can be negative if the bar is taller than boundaries.

Reality: Trapped water volume is never negative; if calculation yields negative, it means zero water trapped there.

Why it matters: Failing to clamp negative values to zero leads to wrong total water calculations.

Expert Zone

1

The two-pointer method implicitly uses the fact that the smaller boundary determines water level, allowing pointer movement without missing trapped water.

2

Precomputing max arrays is easier to implement but uses extra memory, which can be critical in memory-constrained environments.

3

Edge cases like flat or strictly increasing/decreasing arrays reveal that trapped water is zero, and the algorithm handles these naturally without special cases.

When NOT to use

Avoid the two-pointer method if you need to track trapped water at each position separately for further processing; in such cases, precomputing max arrays is better. Also, if the input is streaming or very large and cannot be stored fully, consider online algorithms or approximations.

Production Patterns

In real systems, this problem appears in terrain modeling, urban drainage design, and game development for water simulation. Professionals often use the two-pointer method for its efficiency and implement additional checks for input validation and edge cases.

Connections

Dynamic Programming

Builds-on

Precomputing max arrays is a form of dynamic programming where overlapping subproblems (max heights) are stored to avoid recomputation.

Sliding Window Technique

Similar pattern

Both use pointers moving through arrays to maintain information about a range, optimizing time complexity.

Civil Engineering - Water Drainage

Real-world application

Understanding how water traps between barriers helps design effective drainage systems and flood prevention.

Common Pitfalls

#1 Calculating trapped water without considering the minimum of left and right max heights.

Wrong approach:

for (int i = 0; i < height.length; i++) {
int leftMax = findMaxLeft(i);
trappedWater += leftMax - height[i]; // Missing right max consideration
}

Correct approach:

for (int i = 0; i < height.length; i++) {
int leftMax = findMaxLeft(i);
int rightMax = findMaxRight(i);
trappedWater += Math.min(leftMax, rightMax) - height[i];
}

Root cause:

Misunderstanding that both sides limit water trapping, not just one.

#2 Using nested loops without optimization for large inputs.

Wrong approach:

for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
// find left max
}
for (int k = i; k < n; k++) {
// find right max
}
}

Correct approach:

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

Root cause:

Not recognizing repeated work and how to optimize with extra space.

#3 Not handling empty or single-element arrays.

Wrong approach:

int trap(int[] height) {
// no check for empty array
int left = 0, right = height.length - 1;
// code continues
}

Correct approach:

if (height == null || height.length < 3) return 0;
// proceed with algorithm

Root cause:

Ignoring edge cases leads to runtime errors or incorrect results.

Key Takeaways

Trapped water at any position depends on the smaller of the tallest bars to its left and right minus the bar's own height.

The brute force method works but is inefficient; precomputing max arrays or using two pointers optimizes time and space.

The two-pointer technique achieves O(n) time and O(1) space by moving inward from both ends and updating max boundaries on the fly.

Edge cases like empty or uniform height arrays naturally result in zero trapped water and are handled gracefully by the optimal solution.

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

Practice

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

easy

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

B. The maximum height of the bars in the array

C. The minimum height of the bars in the array

D. The number of bars that are taller than their neighbors

Solution

1. Step 1: Understand the problem statement

   The problem asks to calculate how much water can be trapped between bars of different heights after it rains.

2. Step 2: Identify the goal

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

3. Final Answer:

   The total amount of water that can be trapped between the bars after raining -> Option A

4. Quick Check:

   Trapping rain water = total trapped water volume [OK]

Hint: Focus on trapped water volume, not bar heights [OK]

Common Mistakes:

• Confusing trapped water with max bar height
• Counting bars taller than neighbors instead of water
• Calculating minimum height instead of trapped water

2. Which of the following Java code snippets correctly initializes an array of heights for the Trapping Rain Water problem?

easy

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

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

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

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

Solution

1. Step 1: Check Java array initialization syntax

   In Java, arrays are initialized with curly braces {} and type declaration like int[].

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 B, C, and D use invalid syntax.

3. Final Answer:

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

4. Quick Check:

   Java array init uses {} with type[] [OK]

Hint: Use curly braces {} with type[] to initialize arrays [OK]

Common Mistakes:

• Using square brackets [] without type[]
• Using parentheses () instead of braces {}
• Trying to initialize array with new int(size) and values together

3. What is the output of the following Java code snippet for trapping rain water?

int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println(trap(height));

public static int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (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. 5

B. 6

C. 7

D. 8

Solution

1. Step 1: Understand two-pointer approach

   We use two pointers left and right, track max heights on both sides, and add trapped water where possible.

2. Step 2: Trace the code with given input

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

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Two-pointer trap calculation = 6 [OK]

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

Common Mistakes:

• Not updating leftMax and rightMax correctly
• Adding negative water amounts
• Confusing left and right pointer movements

4. Identify the bug in this Java method for trapping rain water:

public static int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (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. The water calculation should add height[left] instead of subtracting

B. The comparison should be 'height[left] <= height[right]' instead of '<'

C. The loop condition should be 'left < right' instead of 'left <= right'

D. leftMax and rightMax should be initialized to 1 instead of 0

Solution

1. Step 1: Analyze loop condition impact

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

2. Step 2: Correct loop condition

   Changing to 'left < right' prevents overlapping pointers and avoids incorrect water calculation.

3. Final Answer:

   The loop condition should be 'left < right' instead of 'left <= right' -> Option C

4. Quick Check:

   Loop condition 'left < right' avoids overlap [OK]

Hint: Use strict less than in loop to avoid pointer overlap [OK]

Common Mistakes:

• Using <= causes double counting at same index
• Changing comparison operators incorrectly
• Initializing max heights incorrectly

5. Given the height array {3, 0, 2, 0, 4}, what is the total trapped rain water? Explain how the trapped water is calculated step-by-step.

hard

A. 7

B. 6

C. 5

D. 8

Solution

1. Step 1: Calculate leftMax and rightMax arrays

   leftMax = [3, 3, 3, 3, 4], rightMax = [4, 4, 4, 4, 4]

2. Step 2: Calculate trapped water at each index

   Water trapped = min(leftMax[i], rightMax[i]) - height[i] = [0, 3, 1, 3, 0] Sum = 0 + 3 + 1 + 3 + 0 = 7

3. Step 3: Re-check calculation for correctness

   At index 1: min(3,4)-0=3 At index 2: min(3,4)-2=1 At index 3: min(3,4)-0=3 Sum = 7 units trapped water

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Sum trapped water = 7 units [OK]

Hint: Use leftMax and rightMax arrays to find trapped water [OK]

Common Mistakes:

• Forgetting to take minimum of leftMax and rightMax
• Subtracting height incorrectly
• Not summing trapped water at all indices