Trapping Rain Water Leetcode

This question is taken by LeetCode. You can find question detail by the below link.

Let’s write an optimized solution to this problem.

https://leetcode.com/problems/trapping-rain-water/

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

Example 2:

Input: height = [0, 1, 0, 2, 1, 0, 3, 1, 0, 1, 2]
Output: 8

💡 This problem is like a critical thinking puzzle where you have to look at the basic information that’s in front of you and see if you can think deeply and derive some patterns and hints that will guide you towards knowing what technical tricks or what data structures and algorithms to apply in order to solve this question.

💡 You can see that throughout this bar chart, there are some gaps in space at the very bottom, and that is when an element in the array has zero in its value.
Other than that, there is no actual distance between our bars.

Now, what we have to imagine is that given a chart like this, if rain were to fall down onto this chart, how much water would get trapped?

💡 Well, here I visualized it for you like these blue boxes and all we really have to do is just count the number of blue blocks here and we’ll see that in the first. There’s one blue box in the first blue area, in the second blue area, there are three blocks and then in the third blue area, there are four blue blocks of water. So you just add that together, 1 + 3 + 4, which gives us 8.
And that’s what we return as the answer. So there is 8 unit of water.

Trapping Rain Water Leetcode

💡 First way – Brute Force solution

const trappingRainWaterAreaFirstWay = (arr) => {
  let totalWater = 0;
  for (let i = 0; i < arr.length; i++) {
    let left = i,
      right = i,
      maxLeft = 0,
      maxRight = 0;
    while (left >= 0) {
      maxLeft = Math.max(arr[left], maxLeft);
      left--;
    }
    while (right < arr.length) {
      maxRight = Math.max(arr[right], maxRight);
      right++;
    }
    const minHeight = Math.min(maxLeft, maxRight);
    const currentWater = minHeight - arr[i];
    if (currentWater > 0) {
      totalWater += currentWater;
    }
  }
  return totalWater;
};

💻 Execute program

trappingRainWaterAreaFirstWay([0, 1, 0, 2, 1, 0, 3, 1, 0, 1, 2])

trappingRainWaterAreaFirstWay([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])

trappingRainWaterAreaFirstWay([4, 2, 0, 3, 2, 5])

8
6
9

 * Runtime: 168 ms
* Memory Usage: 40.4 MB

 * Time: O(n^2) 
* Space: O(1)

💡 Second way: Optimized version

const trappingRainWaterAreaSecondWay = (arr) => {
  let totalWater = 0;
  let left = 0,
    right = arr.length - 1,
    maxLeft = 0,
    maxRight = 0;

  while (left < right) {
    if (arr[left] <= arr[right]) {
      maxLeft = Math.max(maxLeft, arr[left]);
      // when current height is less then max Left, means there is some space above current height where water can store.
      if (arr[left] < maxLeft) {
        totalWater += maxLeft - arr[left];
      }
      left++;
    } else {
      maxRight = Math.max(maxRight, arr[right]);
      if (arr[right] < maxRight) {
        totalWater += maxRight - arr[right];
      }
      right--;
    }
  }

  return totalWater;
};

💻 Run Program:

trappingRainWaterAreaSecondWay([0, 1, 0, 2, 1, 0, 3, 1, 0, 1, 2])

trappingRainWaterAreaSecondWay([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])

trappingRainWaterAreaSecondWay([4, 2, 0, 3, 2, 5])

Output >
8
6
9

 * Runtime: 72 ms 
* Memory Usage: 40.2 MB

 * Time: O(n)
 * Space: O(1)

✔ JavaScript Rotate 2D matrix 90 degrees clockwise | Top Interview Question

✔ HashTable Data Structure in JavaScript with Add Delete & Search Algorithms

✔ Trie Data Structure – Insert Search Delete & Print Program with JavaScript

✔ Top JavaScript Commonly asked Algorithms in Interview

✔ JavaScript String Permutation Program with nice explanation

Array Representation of Binary Tree | Full Tree & Complete Binary Tree