Trapping Rain Water

Array, Two Pointers

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 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length

  • 1 <= n <= 2 * 104

  • 0 <= height[i] <= 105

Assumptions:

  • There is no number calculation overflow.

  • There is no any negative value element.

Questions to Clarify:

  • What would be the size of the input array?

Solutions

The problem is about calculating the total amount of rainwater that can be trapped between bars of different heights. The solution involves iterating over each bar and calculating the amount of water that can be trapped on top of it.

For each bar, we find the maximum height of the bars to its left and right. The water that can be trapped on top of the current bar is the minimum of these two maximum heights minus the height of the current bar. This is because the water level cannot be higher than the shorter bar around it, and the height of the bar itself occupies space where water could have been trapped.

Approach – Brute Force Technique

This algorithm calculates the water trapped at each index by finding the maximum height of bars on the left and right side. The water trapped at a particular index is the minimum of these two maximum heights minus the height at that index.

Here, the area calculation formula for this problem is:

maxWater += min(maxLeft,maxRight) - height[current]

Steps

  1. Initialize totalWater to 0: This variable will keep track of the total amount of water that can be trapped.

  2. Iterate over each bar (from 0 to length of the array): For each bar, we calculate the amount of water that can be trapped on top of it.

  3. Find the maximum height of the bars on the left of the current bar: We initialize leftMax to 0 and iterate from the current bar to the first bar of the array, updating leftMax with the maximum height encountered.

  4. Find the maximum height of the bars on the right of the current bar: Similarly, we initialize rightMax to 0 and iterate from the current bar to the last bar of the array, updating rightMax with the maximum height encountered.

  5. Calculate the water trapped on the current bar: The amount of water that can be trapped on the current bar is the minimum of leftMax and rightMax minus the height of the current bar. This is because the water level cannot be higher than the shorter bar around it, and the height of the bar itself occupies space where water could have been trapped.

  6. Add the water trapped on the current bar to totalWater: We add the amount of water trapped on the current bar to totalWater.

  7. Return totalWater: After the loop finishes, totalWater will be the total amount of water that can be trapped according to the input array.

public class Solution
{
    public int Trap(int[] height)
    {

        int maxWater = 0;
        if (height != null && height.Length > 2)
        {
            for (int i = 0; i < height.Length; i++)
            {
                int leftP = i;
                int rightP = i;
                int maxLeft = 0;
                int maxRight = 0;

                while (leftP >= 0)
                {
                    maxLeft = Math.Max(maxLeft, height[leftP]);
                    leftP--;
                }

                while (rightP < height.Length)
                {
                    maxRight = Math.Max(maxRight, height[rightP]);
                    rightP++;
                }

                maxWater += Math.Min(maxLeft, maxRight) - height[i];
            }
        }

        return maxWater;
    }
}

Complexity

  • Time complexity: O(N^2)

  • Space complexity: O(1)

Approach – Two Pointers Technique

The problem is about calculating the total amount of rainwater that can be trapped between bars of different heights. The solution involves using two pointers, one starting from the beginning of the array (left) and the other from the end of the array (right).

The algorithm maintains two variables, maxLeft and maxRight, to keep track of the maximum height of the bars seen so far from the left and right, respectively.

In each step, the algorithm compares maxLeft and maxRight. If maxLeft is less than maxRight, it means the water trapped on the bar at the left index would be maxLeft - height[left], because maxLeft is the minimum of the two. So, it adds this to totalWater and moves the left pointer one step to the right.

If maxLeft is not less than maxRight, it does the same operation with the right pointer and maxRight.

The algorithm continues this process until the left and right pointers meet. At the end, totalWater will be the total amount of water that can be trapped according to the input array.

Steps

  1. Check if the array length is less than or equal to 2: If the array length is less than or equal to 2, there can't be any trapped water, so return 0.

  2. Initialize variables: n is the length of the array. maxLeft and maxRight are the maximum heights of the bars on the left and right ends of the array, respectively. left and right are pointers to the second bar from the left and the second bar from the right, respectively. totalWater is initialized to 0 to keep track of the total amount of trapped water.

  3. Start a while loop that continues as long as left is less than or equal to right: This loop traverses the array from both ends towards the center.

  4. Check if maxLeft is less than maxRight: If maxLeft is less than maxRight, then the water trapped on the current bar depends on maxLeft.

    • If the height of the bar at the left index is greater than maxLeft, update maxLeft to this height.

    • Otherwise, add maxLeft - height[left] to totalWater (this is the amount of water that the current bar can trap), and increment left by 1.

  5. If maxLeft is not less than maxRight, then the water trapped on the current bar depends on maxRight.

    • If the height of the bar at the right index is greater than maxRight, update maxRight to this height.

    • Otherwise, add maxRight - height[right] to totalWater (this is the amount of water that the current bar can trap), and decrement right by 1.

  6. Return totalWater: After the loop finishes, totalWater will be the total amount of water that can be trapped according to the input array.

public class Solution
{
    public int Trap(int[] height)
    {

        if (height?.Length <= 2) return 0;

        int n = height!.Length, maxLeft = height[0], maxRight = height[n - 1];
        int left = 1, right = n - 2, totalWater = 0;
        while (left <= right)
        {
            if (maxLeft < maxRight)
            {
                if (height[left] > maxLeft)
                    maxLeft = height[left];
                else
                    totalWater += maxLeft - height[left];
                left += 1;
            }
            else
            {
                if (height[right] > maxRight)
                    maxRight = height[right];
                else
                    totalWater += maxRight - height[right];
                right -= 1;
            }
        }
        return totalWater;
    }
}

Complexity

  • Time complexity: O(N)

  • Space complexity: O(1)

Previous3SumNextMaximum sum of a subarray

Last updated