42. Trapping Rain Water
MD ARIFUL HAQUE
Posted on May 3, 2024
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:
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;
}
}
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!
Posted on May 3, 2024
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
