42. Trapping Rain Water

 

Efficiently Solving the Trapping Rain Water Problem on LeetCode

Introduction

The Trapping Rain Water problem is a popular algorithmic challenge that can be found on LeetCode. It involves calculating how much water can be trapped after it rains, given an array representing the elevation map of a terrain. In this post, we'll walk through an efficient solution that utilizes the two-pointer approach to solve this problem in linear time.

Problem Statement

Given an array height representing the elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Intuition

To solve this problem, the key insight is to determine the amount of water that can be trapped above each bar. This can be achieved by calculating the maximum heights to the left and right of each bar. The amount of water trapped above a bar is determined by the minimum of these two heights, minus the height of the bar itself.

Approach

Our approach involves using two auxiliary arrays to store the maximum heights to the left and right of each bar, respectively. Here’s a step-by-step breakdown:

  1. Initialize Arrays:

    • We initialize two arrays, leftHigh and rightHigh, to keep track of the maximum heights to the left and right of each bar.

  2. Calculate Left High:

    • We traverse the array from left to right to fill the leftHigh array with the maximum height encountered so far.

  3. Calculate Right High:

    • We traverse the array from right to left to fill the rightHigh array with the maximum height encountered so far.

  4. Calculate Trapped Water:

    • We iterate through the elevation map, and for each bar, we compute the amount of water that can be trapped on top of it by taking the minimum of the maximum heights to the left and right of the bar and subtracting the height of the bar itself.

LeetCode Solution

Here's the complete JavaScript solution for the Trapping Rain Water problem:

javascript
var trap = function(height) {
    let n = height.length;
    let rightHigh = Array(n);
    let leftHigh = Array(n);
    // calculate the left High
    leftHigh[0] = height[0];
    for(let i = 1; i < n; i++) {
        leftHigh[i] = Math.max(height[i], leftHigh[i - 1]);
    }
    // calculate the right High
    rightHigh[n -1] = height[n - 1];
    for(let i = n - 2; i >= 0; i--) {
        rightHigh[i] = Math.max(height[i], rightHigh[i + 1]);
    }
    // calculate the result
    let result = 0;
    for(let i = 0; i < n; i++) {
        result += Math.min(leftHigh[i], rightHigh[i]) - height[i];
    }
    return result;
};

Complexity Analysis

Time Complexity: O(n)

  • Calculating the leftHigh array takes O(n) time.

  • Calculating the rightHigh array takes O(n) time.

  • Calculating the trapped water takes O(n) time.

  • Overall, the time complexity is linear, O(n).

Space Complexity: O(n)

  • The space required for the leftHigh and rightHigh arrays is O(n).

  • Overall, the space complexity is linear, O(n).

Conclusion

This solution efficiently solves the Trapping Rain Water problem by using auxiliary arrays to keep track of the maximum heights to the left and right of each bar and calculating the trapped water in linear time and space. This approach ensures that the solution is efficient even for large input sizes.

If you have any questions or suggestions, feel free to leave a comment. Happy coding!

For those interested in further details or alternative solutions to the Trapping Rain Water problem, you can check out this Trapping Rain Water - LeetCode which offers a simple and efficient approach with a time complexity of 

O(n)O(n).

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

LeetCode Problem: Implement pow(x, n) leetcode:- 50

Understanding the Fast Exponentiation Algorithm: Exponentiation by Squaring In this blog post, we will explore the implementation of the myPow function, a common problem found on LeetCode. The goal of this problem is to compute \(x^n\) efficiently, even when \(n\) is a very large number. Instead of using a naive approach, we employ a method called Exponentiation by Squaring to significantly reduce the number of multiplications required. Problem Overview Given a floating-point number x and an integer n , our task is to implement a function that computes \(x^n\). A straightforward solution might involve multiplying x by itself n times, but this approach is too slow when n is large. Intuition Behind Exponentiation by Squaring The main idea is to reduce the problem size by halving the exponent at each recursive step. Consider the following: If n is even, then: \(x^n = x^{...
Read more