Day 26 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#42. Trapping Rain Water(Hard/JavaScript)

Intro: I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:

• Pick a leetcode problem randomly or Online Assessment from targeted companies.
• Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
• Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
• Code out the solution in LeetCode without looking at the solutions
• Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.

42. Trapping Rain Water
Difficulty: Hard Language: JavaScript

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

Solution(Two pointers):
Key to this method is compare the height of bar on the left end (index 0) and right end (index length - 1).

• If the bar on the right end is taller, start calculating water being trapped from the left end (the lower end). Because it is guaranteed that the water will be trapped at the lower level until a new height shows up that makes the left end taller than the right end.
• If the bar on the left end is taller or equal to the right end, we will calculater the water from the right end (the lower end)

var trap = function(height) {
    let leftMax = 0;
    let rightMax = 0;
    let result = 0;
    let left = 0;
    let right = height.length - 1;

//Initialize variables to keep track of starting from the left end
//(index 0) and the right end (index height.length - 1)(note 2).

    while(left < right) {

//while (note 1) left index is smaller than right index, loop
//continues.

        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);

//Max height (note 5) of left and right end bar will be updated as
//the index updates.

        if(height[left] < height[right]) {
            result += leftMax - height[left++];

//If the bar on the right end is taller, get the amount of trapped
//water by substracting height of next bar from current left max
//height. For example, give height [4,2,0,3,2,5], right bar '5' is
//taller than left bar '4'; it is guaranteed that the water will
//be trapped between these two bars until a new height shows up
//that makes the left end taller than the right end. Since all
//bars in between are less than 4 in this case. The left max
//remains at 4 and left index continue moves to the right
//(left++)(note 4); we will be adding (note 6) the total of 
//'4-2', '4-0','4-3','4-2' to our 'result' to get amount of
//trapped water. 

        } else {
            result += rightMax - height[right--];

//If the bar on the left end is taller or equal to the right end,
//we will calculater the water from the right end (the lower end).
//And move index towards left (right--) (note 3).

        }
    }
    return result;
};

• Time Complexity - O(n)
• Space Complexity - O(1)

References:
LeetCode Problem Link
LeetCode Discussion: Hongbo-Miao
LeetCode Discussion: ShashwatBangar
Youtube: TerribleWhiteboard
Note 1: while Loop
Note 2: Array.length
Note 3: Decrement (--)
Note 4: Increment (++)
Note 5: Math.max()
Note 6: Addition Assignment(+=)
Blog Cover Image Credit