Trapping Rain Water - Solution In JavaScript

Trapping Rain Water is a well-known leetcode algorithmic problem in computer science that involves finding the amount of water that can be trapped between walls, given their heights. In this tutorial, we will explore how to solve the Trapping Rain Water problem in JavaScript. It has been asked in many coding interviews.

Understanding the Problem

Before we start coding, let's first understand the problem. We are given an array of integers that represent the heights of walls. We need to find the amount of water that can be trapped between the walls. The walls may not be of the same height, and they can be of any width.

To solve this problem, we need to find the maximum height of the walls on the left and the right of each wall. Once we have these heights, we can determine the amount of water that can be trapped between the walls. Let's look at an example to understand this better.

Example

Suppose we have an array of heights [0,1,0,2,1,0,1,3,2,1,2,1]. We can represent this array as follows:

  | |
_|_|_|_| |  | |
0 1 0 2 1 0 1 3 2 1 2 1

The '|' represents the wall and the '_' represents the water that can be trapped between the walls. To calculate the amount of water that can be trapped, we first need to find the maximum height of the walls on the left and right of each wall. For example, the maximum height on the left of the first wall (height 0) is 0 and the maximum height on the right is 1. Therefore, the amount of water that can be trapped between the first wall and the second wall is 1 - 0 - 1 = 0. Similarly, the maximum height on the left of the fourth wall (height 2) is 1 and the maximum height on the right is 3. Therefore, the amount of water that can be trapped between the fourth wall and the eighth wall is 2 - 1 - 1 = 0. We repeat this process for all the walls and add up the amount of water that can be trapped to get our final answer. In this case, the amount of water that can be trapped is 6 units. Solving the Problem in JavaScript Now that we understand the problem, let's solve it in JavaScript. We will use a two-pointer approach to find the maximum height on the left and right of each wall. We will start with two pointers, one at the beginning and one at the end of the array. We will then compare the height of the walls at these two pointers and move the pointer with the smaller height towards the center. We will keep track of the maximum height on the left and right of each wall as we move the pointers.

Here is the JavaScript code for solving the Trapping Rain Water problem:

Code

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

  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] > leftMax) {
        leftMax = height[left];
      } else {
        water += leftMax - height[left];
      }
      left++;
    } else {
      if (height[right] > rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }

  return water;
}

To test the function, we can pass in an array of heights and log the result to the console:

const heights = [0,1,0,2,1,0,1,3,2,1,2,1];
const water = trap(heights);
console.log(water); // Output: 6

This code will output the amount of water that can be trapped between the walls in the given array of heights, which in this case is 6 units.