Zig-Zag World of Algorithm and Data Structures: [Uber][LeetCode] Trapping Rain Water

Tuesday, August 18, 2015

[Uber][LeetCode] Trapping Rain Water

Problem: 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
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.

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

Approach: Basically if we see the problem closely, we can easily figure out that the trapped water amount at any bar 'i' is as follows:

water(i) = Min (max height among all the bar in left of i, max height among all the bars in right of i ) - height(i)

We just need the sum of all of these amount to get the answer. We can achieve it using brute force approach but let's try to do better:

we can pre calculate the max height from left for every i and store in an array say leftMax and we can do the same from the right and store it in the array say rightMax. Now the calculation is something like this:

FOR i = 1 TO n

water += ( Min(leftMax[i], rightMax[i]) - height[i])

This approach will solve the problem in linear time but if you see it is taking extra space. Let's try to reduce it. The intuition is if till leftMax is greater than rightMax, we just calculate according to rightMax only right? (see above, we take the min only). Same thing we can say about when rightMax is greater than leftMax.

Now we can use two pointer approach one from left (index = 0) and one from right(index = n - 1) and can follow the following steps:

WHILE left < right

IF height[left] < height[right]

IF height[left] > leftMax //. can't trap water

leftMax = height[left]

ELSE

water += leftMax - height[left]

++left;

ELSE

// same for right
--right

Implementation in C#:

Approach 1:

public int Trap(int[] height)

{

int length = height?.Length ?? 0;

if (length <= 1)

{

return 0;

}

int[] leftMax = new int[length];

leftMax[0] = height[0];

for (int i = 1; i < length; ++i)

{

leftMax[i] = Math.Max(leftMax[i - 1], height[i]);

}

int[] rightMax = new int[length];

rightMax[length - 1] = height[length - 1];

for (int i = length - 2; i >=0; --i)

{

rightMax[i] = Math.Max(rightMax[i + 1], height[i]);

}

int sum = 0;

for (int i = 1; i < length - 1; ++i)

{

sum += (Math.Min(leftMax[i], rightMax[i]) - height[i]);

}

return sum;

}

Approach 2:

    public int Trap(int[] height)
    {
        int length = height?.Length ?? 0;
        if (length <= 2)
        {
            return 0;
        }
        int water = 0;
        int leftMax = 0, rightMax = 0;
        int left = 0, right = length - 1;
        while (left < right)
        {
            if (height[left] < height[right])
            {
                if (height[left] <= leftMax)
                {
                    water += leftMax - height[left];
                }
                else
                {
                    leftMax = height[left];
                }
                ++left;
            }
            else
            {
                if (height[right] <= rightMax)
                {
                    water += rightMax - height[right];
                }
                else
                {
                    rightMax = height[right];
                }
                --right;
            }
        }
        return water;
    }