226. Trapping Rain Water
Hard
Two Pointers
Array
Problem
Given n non-negative integers representing an elevation map where the width of each bar is 1, return how much rain water can be trapped after raining.
Examples
Example 1
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Example 2
Input: [4,2,0,3,2,5]
Output: 9
Example 3
Input: [1,2,3]
Output: 0
Constraints
� 1 <= height.length <= 20000
� 0 <= height[i] <= 100000
Hints
?? Water above a position depends on the smaller of the maximum heights to its left and right.
?? You do not need full prefix and suffix arrays.
?? Maintain leftMax and rightMax while moving two pointers inward.
Expected Complexity
Time: O(n)
Space: O(1)
Follow-up
Can you solve it with O(1) auxiliary space?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[0,1,0,2,1,0,1,3,2,1,2,1]Expected
6