This is a very interesting algorithm we will be going to solve this problem. Let's begin with understanding the problem.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after rain.

For example, Given [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], return 6.

The above elevation map is represented by an array [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. In this case, 6 units of rain water (blue section) are trapped.

Let's start with the algorithm,

const trap = height => {

const n = height.length;

const left = [];

const right = [];

let leftMax = 0;

let rightMax = 0;

for (let i = 0, j = n - 1; i < n, j >= 0; i++, j--) {

// Scan from left

left[i] = leftMax;

leftMax = Math.max(leftMax, height[i]);

// Scan from right

right[j] = rightMax;

rightMax = Math.max(rightMax, height[j]);

}

let total = 0;

for (let i = 0; i < n; i++) {

let water = Math.min(left[i], right[i]) - height[i];

total += water > 0 ? water : 0;

}

return total;

}

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));

Here, we have data in the form of an array. We have passed this array from the loop in both directions from left to right and right to left. Inside the loop, we are storing the maximum number from the array one by one in the different arrays from the left and the same from the right.

This will provide us an array of the maximum left side of elements and the maximum right side of the element. In the second loop, we are calculating water that can be stored after subtracting the height from the minimum of right and left elements.

I hope you understood the algorithm, if you have any doubt let us know in the comments.

## 0 Comments