Trapping Rainwater
BloomBerg
PhonePe
WalmartThe problem
Given an array of non-negative integers, height representing the elevation of ground. Calculate the amount of water that can be trapped after rain.
Input: height= [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6 Explanation: As seen from the diagram 1+1+2+1+1=6 unit of water can be trapped
Input: height= [4, 2, 0, 3, 2, 5] Output: 9 Expalanation: 2+4+1+2=9 unit of water can be trapped
Input: height= [7, 4, 0, 9]
- n == height.length
- 1 <= n <= 105
- 0 <= height[i] <= 105
cpp
class Solution
{
public:
int trap(vector<int> &height){
}
};java
class Solution {
public int trap(int[] height) {
}
}python
class Solution:
def trap(self, height):javascript
class Solution {
trap(height) {
}
}csharp
public class Solution
{
public int trap(int[] height)
{
}
}go
func trap(height []int) int {
}Stuck? Show a way to structure it+
- 01Keep pointers at both ends with the greatest wall seen from each side.
- 02Advance the side with the smaller maximum because that side's water is already determined.
- 03Add the difference between that maximum and the current height.
- 04Update the side maximum before or alongside advancing that pointer.
Reference answer
Then expect these follow-ups
Why is the smaller side's trapped water already determined?
Tests: two-pointer proof
How would the stack-based solution work?
Tests: alternative approach
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question