Trapping Rainwater

Problem Overview

The "Trapping Rain Water" problem is a classic algorithmic challenge that often appears in technical interviews involving arrays and linked lists. The task is to determine the amount of water that can be trapped between non-negative integer columns, representing elevation heights on a contour after it rains. Each unit of elevation is equivalent to a width and height of 1.

Problem Statement

Given ( n ) non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

The above input gives a visual contour with several trapped water units.

Understanding the Problem

The concept of trapping rainwater between elevations can be visualized by considering each column, checking the tallest barriers to its left and right, and calculating water retained over that column. Water can exist over a column where both sides have taller columns, creating potential traps.

Visualizing the example, here is how water traps:

Elevation: 0 1 0 2 1 0 1 3 2 1 2 1
Water:     0 0 1 0 1 2 1 0 0 1 0 0

The units of water get trapped in areas between higher bar elevations forming pockets.

Key DSA Concepts and Theory

Arrays

This problem heavily relies on array structures to hold bar heights and sequentially process elevation data. Arrays offer direct index access, which enables efficient height comparisons.

Two Pointers Technique

The two-pointer technique helps in approaching this problem optimally. By using pointers, one from the start and one from the end, we can iterate inward and efficiently compute water trapped without excessive recalculations.

Dynamic Programming (Prefix and Suffix Arrays)

To avoid repetitive calculations, prefix and suffix arrays precompute the maximum heights from each direction. This is a fundamental dynamic programming strategy to minimize redundant computations.

Solution Approach

To solve the problem efficiently, we leverage the two-pointer technique, considering dynamic programming insights:

1. Initialize Pointers and Variables:

   • Set up two pointers (left and right), initializing them to the start and end of the array.
   • Maintain left_max and right_max to store the max elevation to the left and right of the pointers respectively.
   • A variable water_trapped will accumulate the total water.

2. Iterate Using Two Pointers:

   • Move the pointers inward based on height comparisons:
     • If the height at left is less than right, check for water trapping condition at left:
       • Update left_max.
       • Calculate water based on left_max if higher than current height.
       • Update left pointer.
     • Else, similarly handle the right pointer, updating right_max and calculating water.

3. Calculate Trapped Water:

   • Water trapped at any column is the difference between current bar height and the minimum of left_max and right_max.

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int trap(vector<int>& height) {
    int n = height.size();
    if (n < 3) return 0; // No space for water

    int left = 0, right = n - 1;
    int left_max = 0, right_max = 0;
    int water_trapped = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];
            } else {
                water_trapped += (left_max - height[left]);
            }
            left++;
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];
            } else {
                water_trapped += (right_max - height[right]);
            }
            right--;
        }
    }

    return water_trapped;
}

int main() {
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    cout << "Water trapped: " << trap(height) << " units." << endl;
    return 0;
}

Java Code

public class TrappingRainWater {

    public int trap(int[] height) {
        int n = height.length;
        if (n < 3) return 0; // No space for water

        int left = 0, right = n - 1;
        int left_max = 0, right_max = 0;
        int water_trapped = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    water_trapped += (left_max - height[left]);
                }
                left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    water_trapped += (right_max - height[right]);
                }
                right--;
            }
        }

        return water_trapped;
    }

    public static void main(String[] args) {
        TrappingRainWater solver = new TrappingRainWater();
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("Water trapped: " + solver.trap(height) + " units.");
    }
}

Time and Space Complexity Analysis

• Time Complexity: ( O(n) ) because each element is processed at most twice by the two pointers.

• Space Complexity: ( O(1) ) since additional space is used only for a few variables, regardless of input size.

Common Mistakes to Avoid

• Forgetting to check if the array length is less than 3, which doesn't allow water to be trapped.
• Misplacing the conditions to update pointers and sometimes iterating indexes improperly can lead to incorrect results.

Similar Problems on LeetCode

1. Container With Most Water (LeetCode #11)
2. Largest Rectangle in Histogram (LeetCode #84)
3. Trapping Rain Water II (LeetCode #407)

Additional Resources and References

• LeetCode Article on Two-Pointer Techniques.
• Dynamic Programming Primer.

By understanding and coding through this problem approach, you can deepen your knowledge of array manipulation and dynamic programming, key components in efficient algorithm design.