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

The Future of AI, LLMs, and Observability on Google Cloud

Datadog sat down with Google’s Director of AI to discuss the current and future states of AI, ML, and LLMs on Google Cloud. Discover 7 key insights for technical leaders, covering everything from upskilling teams to observability best practices

Learn More

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 →