JavaScript Coding Test Course, Calculating the Amount of Water

Problem Definition

The problem is to calculate the amount of water that can be collected when it rains, given an array of heights of bars. The heights of the bars are provided as each element of the array.

For example, if the array is [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the amount of water that can be collected is 6. Visually representing how water is stored between each bar in this example is as follows:

Approaches to Solve the Problem

There are various methods that can be used to solve this problem. The two most commonly used approaches are as follows.

1. Two Pointers Method

   This method progresses by moving two pointers inwards from both ends. Each pointer tracks the height from the left and right, allowing calculation of positions where water can accumulate.

2. Dynamic Programming

   This method involves finding the tallest bar from both left and right at each position, using the shorter of the two to calculate the amount of water. However, this method has the drawback of using a lot of additional memory.

Solving the Problem with JavaScript

First, let’s implement the code using the two pointers method. We will create an algorithm that starts from both ends of the array and moves towards the center to calculate the amount of water.

Code Example

function trap(height) {
    if (height.length === 0) return 0;

    let left = 0;
    let right = height.length - 1;
    let leftMax = 0;
    let rightMax = 0;
    let waterTrapped = 0;

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

    return waterTrapped;
}

            

The above function takes the height array as input and calculates the amount of water that can be collected after it rains.

Code Explanation

Let’s take a step-by-step look at the above code:

1. Initialization: left is initialized to 0, and right is initialized to the last index of the array (length – 1). leftMax and rightMax store the maximum heights from their respective directions. waterTrapped indicates the final amount of water collected.
2. Loop Execution: The loop runs until left is less than right. In each iteration, the heights from the left and right are compared to calculate the amount of water from the lower side.
3. Water Calculation: If the height from the left is lower, it compares the maximum height on the left with the current height to calculate the amount of water that can be stored. Similarly, the same operation is performed on the right side.
4. Return Result: After all loops are completed, it returns the waterTrapped variable to output the final result.

Code Testing

Now, let’s test the algorithm we’ve written. We can verify the performance of the function through several examples like the following:

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(trap([4, 2, 0, 3, 2, 5])); // 9
console.log(trap([])); // 0
console.log(trap([1, 0, 1])); // 1

            

Each output should match the predicted amount of water. The following results will be displayed:

• trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) – 6
• trap([4, 2, 0, 3, 2, 5]) – 9
• trap([]) – 0
• trap([1, 0, 1]) – 1

Performance Analysis

The algorithm above has a time complexity of O(n) and a space complexity of O(1). This means that the execution time and space required are proportional to the size of the input array. Therefore, it works efficiently even with large amounts of data.

If dynamic programming is used, it requires an additional array to store heights, resulting in a space complexity of O(n). However, the time complexity remains O(n) as well.

Conclusion

In this lecture, we discussed the ‘Calculating the Amount of Water’ problem and introduced how to solve it using JavaScript. By using the two pointers algorithm, we effectively tackled the problem and also conducted code implementation and performance analysis.

This problem includes important concepts that can be applied to other algorithm problems, so practicing other similar problems can further enhance your algorithm skills.

This concludes the JavaScript coding test lecture. I hope it helps you improve your coding skills!