The Trapping Rain Water problem, as featured on LeetCode 42, asks you to calculate the total amount of water that can be trapped after raining, given an elevation map represented by an array of non-negative integers. Each element in the array represents the height of a bar with a width of 1. Water can be trapped between bars of higher elevation.

For example, given the elevation map [0,1,0,2,1,0,1,3,2,1,2,1], the total amount of trapped water is 6 units.

Brute-Force Approach (O(n²))

A straightforward, albeit inefficient, approach involvse iterating through each bar and for each bar, finding the highest bar to its left and the highest bar to its right. The water trapped at the current bar is determined by the smaller of these two maximum heights minus the height of the current bar.

This method requires nested loops, leading to a time complexity of O(n²), which becomes impractical for large input arrays.

public int TrapRainWaterBruteForce(int[] heights)
{
    int totalWater = 0;
    int n = heights.Length;

    // Iterate through each bar, except the first and last
    for (int i = 1; i < n - 1; i++)
    {
        int currentHeight = heights[i];
        int leftMax = 0;
        int rightMax = 0;

        // Find the maximum height to the left of the current bar
        for (int j = i - 1; j >= 0; j--)
        {
            leftMax = Math.Max(leftMax, heights[j]);
        }

        // Find the maximum height to the right of the current bar
        for (int j = i + 1; j < n; j++)
        {
            rightMax = Math.Max(rightMax, heights[j]);
        }

        // Calculate trapped water at the current position
        int waterLevel = Math.Min(leftMax, rightMax);
        if (waterLevel > currentHeight)
        {
            totalWater += waterLevel - currentHeight;
        }
    }

    return totalWater;
}

Optimized Two-Pointer Approach (O(n))

A more efficient solution uses a two-pointer technique, achieving a linear time complexity of O(n) and constant space complexity of O(1). The strategy involves initializing two pointers, one at the beginning (left) and one at the end (right) of the array. We also maintain two variables, leftMax and rightMax, to store the highest bar encountered from the left and right, respectively.

The algorithm works by moving the pointer that points to the shorter bar. This is because the amount of water trapped is limited by the shorter bar. As we move the pointers inward, we update leftMax and rightMax and calculate the trapped water for the curent position.

public int TrapRainWaterOptimized(int[] heights)
{
    int totalWater = 0;
    int left = 0;
    int right = heights.Length - 1;
    int leftMax = 0;
    int rightMax = 0;

    while (left < right)
    {
        if (heights[left] < heights[right])
        {
            // Process the left side
            if (heights[left] >= leftMax)
            {
                // New maximum on the left
                leftMax = heights[left];
            }
            else
            {
                // Water can be trapped
                totalWater += leftMax - heights[left];
            }
            left++;
        }
        else
        {
            // Process the right side
            if (heights[right] >= rightMax)
            {
                // New maximum on the right
                rightMax = heights[right];
            }
            else
            {
                // Water can be trapped
                totalWater += rightMax - heights[right];
            }
            right--;
        }
    }

    return totalWater;
}