Coding

Trapping Rainwater

Asked at

BloomBerg

PhonePe

Walmart

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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)
    {
        
    }
}

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

Use pointers left and right, plus leftMax and rightMax. At each step, process the side with the smaller current maximum. If leftMax <= rightMax, any water at left is bounded by leftMax regardless of unknown interior bars because the right side already has a boundary at least that high. Add max(0, leftMax - height[left]), update leftMax, and advance left. Otherwise perform the symmetric operation on the right. This takes O(n) time and O(1) space. An easier O(n)-space solution precomputes maximum heights to the left and right of each index and sums min(leftMax[i], rightMax[i]) - height[i]. The two-pointer proof depends on processing the lower established boundary, not simply the lower current bar without maintaining maxima.

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

Hiring now

PhonePe has 114 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer, Backend (3-5 years)
Pune, Maharashtra, India
Software Engineer , Backend (5-7 years)
Pune, Maharashtra, India
Software Engineer, App-Android
Bengaluru, Karnataka, India

Or practice this question first

Next question