LeetCode Challenge: 42. Trapping Rain Water - JavaScript Solution 🚀

Top Interview 150

To solve LeetCode 42: Trapping Rain Water, we need to calculate the total amount of water that can be trapped between elevation heights after it rains. This problem is best tackled using one of the following methods:

---

🚀 Problem Description

Input: An array height where each element represents an elevation bar.
Output: The total units of water trapped.

---

💡 Examples

Example 1

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]  
Output: 6  
Explanation: Water trapped is shown in the diagram.  

Example 2

Input: height = [4,2,0,3,2,5]  
Output: 9  
Explanation: Water trapped in valleys.  

---

🏆 Solution Approach

Two-Pointer Approach

This method uses O(n) time complexity and O(1) space complexity.

---

Implementation

var trap = function(height) {
    let left = 0, right = height.length - 1;
    let leftMax = 0, 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;
};

---

🔍 How It Works

1. Initialization:
   • Two pointers: left and right starting at the two ends of the array.
2. leftMax and rightMax to store the maximum height seen so far from the left and right.
3. Process:
   • Compare height[left] and height[right].
   • If height[left] is smaller, calculate water trapped using leftMax.
   • Otherwise, calculate water trapped using rightMax.
   • Move the pointer inward.
4. Calculation:
   • If the current bar is smaller than leftMax or rightMax, it traps water.

---

🔑 Complexity Analysis

• > Time Complexity: O(n) Single traversal of the height array.
• > Space Complexity: O(1), No additional space is used.

---

📋 Dry Run

Input: height = [4,2,0,3,2,5]

Output: 3

---

📚 Learn More

Read the detailed walkthrough and explanation of the two-pointer approach on my Dev.to post:
👉 Candy - JavaScript Solution

How would you optimize this further? Let’s discuss below! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!