DEV Community

Cover image for 42. Trapping Rain Water
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on • Edited on

42. Trapping Rain Water

42. Trapping Rain Water

Hard

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:

rainwatertrap

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

Solution:

class Solution {

    /**
     * @param Integer[] $height
     * @return Integer
     */
    function trap($height) {
        $result = 0;
        $leftIndex = 0;
        $rightIndex = count($height) - 1;
        $maxLeft = 0;
        $maxRight = 0;
        while ($leftIndex < $rightIndex) {
            if ($height[$leftIndex] < $height[$rightIndex]) {
                $maxLeft = max($maxLeft, $height[$leftIndex]);
                $result += $maxLeft - $height[$leftIndex];
                $leftIndex++;
            } else {
                $maxRight = max($maxRight, $height[$rightIndex]);
                $result += $maxRight - $height[$rightIndex];
                $rightIndex--;
            }
        }
        return $result;
    }
}
Enter fullscreen mode Exit fullscreen mode

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

The Most Contextual AI Development Assistant

Pieces.app image

Our centralized storage agent works on-device, unifying various developer tools to proactively capture and enrich useful materials, streamline collaboration, and solve complex problems through a contextual understanding of your unique workflow.

👥 Ideal for solo developers, teams, and cross-company projects

Learn more

👋 Kindness is contagious

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

Okay