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 Datadog

How to Diagram Your Cloud Architecture

Cloud architecture diagrams provide critical visibility into the resources in your environment and how they’re connected. In our latest eBook, AWS Solution Architects Jason Mimick and James Wenzel walk through best practices on how to build effective and professional diagrams.

Download the Free eBook

Top comments (0)

Billboard image

Create up to 10 Postgres Databases on Neon's free plan.

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Try Neon for Free →