DEV Community

Cover image for LeetCode Challenge: 42. Trapping Rain Water - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

1 1 1 1 1

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.  
Enter fullscreen mode Exit fullscreen mode

Example 2

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

πŸ† 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;
};
Enter fullscreen mode Exit fullscreen mode

πŸ” 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]

Trapping Rain Water
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

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

Top comments (1)

Collapse
 
rahulgithubweb profile image
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!

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

πŸ‘‹ Kindness is contagious

Please leave a ❀️ or a friendly comment on this post if you found it helpful!

Okay