[Leetcode] Trapping Rain Water

42. Trapping Rain Water

Given nnon-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 * 10``4

0 <= height[i] <= 10``5

How to understand?

This problem's solution will find the water trapped after rain, there is array of the non negative integer which is the height. Finding how much water units can be trapped on the heights. Return the water units trapped as the result.

How to approach?

Optimised Brute force

function trap(height: number[]): number {
    if (height.length == 0) return 0;
    let ans = 0;
    let size = height.length;

    let left_max: number[] = new Array(size).fill(0);
    let right_max: number[] = new Array(size).fill(0);

    left_max[0] = height[0];
    for (let i = 1; i < size; i++) {
        left_max[i] = Math.max(height[i], left_max[i - 1]);
    }

    right_max[size - 1] = height[size - 1];
    for (let i = size - 2; i >= 0; i--) {
        right_max[i] = Math.max(height[i], right_max[i + 1]);
    }

    for (let i = 1; i < size - 1; i++) {
        ans += Math.min(left_max[i], right_max[i]) - height[i];
    }

    return ans;
}

1. set ans as 0, size as input array's length.
2. create left_max array and right_max array to store the max value at index i.
3. left_max's 0 index value will be the first item in input array.
4. and start for loop from 1 to input array's length.
5. in for loop, compare the current index's height and the i-1 index's height.
6. and save the bigger value in left_max[i], so left_max array can store the values of the maximum left height.
7. right_max array will have the last index value as last item in input array.
8. and create for loop starting from size-2 to 0, and compare the value of current index item in height array and i+1 item in right_max array.
9. lastly for loop from 1 to size-1 to compare the minmum of the left and right height and get the difference between those and current height item.
10. plus those water units to answer and return the answer.

summary

Get the left max height table, and right max height table first and compare those for minimum value between those and subtract the current height to get the water trapped. T C is On and S C is On.

2 Pointers

function trap(height: number[]): number {
    let left = 0,
        right = height.length - 1;
    let ans = 0;
    let left_max = 0,
        right_max = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            left_max = Math.max(left_max, height[left]);
            ans += left_max - height[left];
            ++left;
        } else {
            right_max = Math.max(right_max, height[right]);
            ans += right_max - height[right];
            --right;
        }
    }
    return ans;
}

1. think of using 2 pointers from each end of the input array.
2. left and right will be 0 and the length-1 value.
3. answer will be the accumulated water units trapped.
4. set left_max height and right_max height as 0.
5. while loop will check if the left is less than right.
6. when left is bigger than right then it will break the loop and return the accumulated answer.
7. if left index item in height array is smaller than right index item in height array, left_max height will be the max value between left_max value and current left index item in height array.
8. and answer will be accumulated by left_max - current left item in height array.
9. move the left pointer to the right side by doing left++.
10. when the left item in height array is bigger than right item in height array, compare right_max height between right_max value and current right index item in height array.
11. answer will be accumulated by right_max height - current right index item height.
12. and decrement right value so it can go left.

summary

T C is On, S C is O 1. This approach is checking max_height value from left side and right side, do not need to save the values in another array to compare those but variables. left and right pointer will meet at the end and that point it will return the water trapped after rain.