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!

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here →

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs