Algocademy Logo

Course Outline

Trapping Rain Water - JavaScript Solution with O(n) Time Complexity


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

Understanding the Problem

The core challenge of this problem is to determine how much water can be trapped between the bars of the elevation map after it rains. This problem is significant in various fields such as civil engineering for designing drainage systems and computer graphics for simulating realistic water effects.

Potential pitfalls include misunderstanding how water is trapped between bars and not accounting for all possible trapped water units.

Approach

To solve this problem, we need to consider the height of the bars and how they form valleys where water can be trapped. A naive solution would involve checking each bar and calculating the trapped water by finding the maximum heights to the left and right of each bar. However, this approach is not optimal as it has a time complexity of O(n^2).

We can optimize this by using two arrays to store the maximum heights to the left and right of each bar, and then use these arrays to calculate the trapped water in a single pass.

Optimized Approach

1. Create two arrays, leftMax and rightMax, to store the maximum heights to the left and right of each bar.

2. Traverse the height array from left to right to fill the leftMax array.

3. Traverse the height array from right to left to fill the rightMax array.

4. Traverse the height array again to calculate the trapped water using the leftMax and rightMax arrays.

Algorithm

Here is a step-by-step breakdown of the algorithm:

  1. Initialize two arrays, leftMax and rightMax, of the same length as the height array.
  2. Fill the leftMax array by traversing the height array from left to right.
  3. Fill the rightMax array by traversing the height array from right to left.
  4. Initialize a variable waterTrapped to 0.
  5. Traverse the height array and for each bar, calculate the trapped water as the minimum of leftMax[i] and rightMax[i] minus height[i].
  6. Add the trapped water for each bar to waterTrapped.

Code Implementation

// Function to calculate the amount of trapped rain water
function trap(height) {
    // Edge case: if the array is empty, return 0
    if (height.length === 0) return 0;

    const n = height.length;
    const leftMax = new Array(n).fill(0);
    const rightMax = new Array(n).fill(0);
    let waterTrapped = 0;

    // Fill leftMax array
    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }

    // Fill rightMax array
    rightMax[n - 1] = height[n - 1];
    for (let i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }

    // Calculate the trapped water
    for (let i = 0; i < n; i++) {
        waterTrapped += Math.min(leftMax[i], rightMax[i]) - height[i];
    }

    return waterTrapped;
}

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

Complexity Analysis

The time complexity of this approach is O(n) because we traverse the height array three times. The space complexity is also O(n) due to the additional arrays leftMax and rightMax.

Edge Cases

Potential edge cases include:

  • Empty array: The function should return 0.
  • Array with all bars of the same height: No water can be trapped.
  • Array with only one bar: No water can be trapped.

These edge cases are handled by the initial check for an empty array and the logic of the algorithm.

Testing

To test the solution comprehensively, consider the following test cases:

  • Simple cases with small arrays.
  • Cases with varying heights and multiple valleys.
  • Edge cases as mentioned above.

Using a testing framework like Jest can help automate and manage these tests effectively.

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to:

  • Break down the problem into smaller parts.
  • Consider edge cases and constraints.
  • Think about optimizing the solution by reducing time and space complexity.

Practicing similar problems and studying different algorithms can help improve problem-solving skills.

Conclusion

Understanding and solving the Trapping Rain Water problem is crucial for developing efficient algorithms. By breaking down the problem, considering edge cases, and optimizing the solution, we can tackle similar challenges effectively.

Keep practicing and exploring different approaches to enhance your problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: