Trapping Rain Water - Google Interview Question - Leetcode 42

Spent a bit more than 2 hours doing this one and some O(N ** 2) solution I came with ended up getting accepted. The whole time I was so worried about knowing where each of those gaps of water started and ended, until I looked for the best solution and noticed there was no need to know that, all I had to know was the maximum amount water that could be trapped in the current position. Great explanation.

This guy seriously just made a hard problem look so easy

My suboptimal o(n) memory solution using the explanation if anyone interested

class Solution:
def trap(self, height: List[int]) -> int:
maxleft = [0] * len(height)
maxright = [0] * len(height)
res = 0

maxleft[0] = height[0]
for i in range(1, len(height)):
maxleft[i] = max(height[i], maxleft[i-1])

maxright[-1] = height[-1]
for i in range(len(height) - 2, -1, -1):
maxright[i] = max(height[i], maxright[i+1])

for i in range(len(height)):
water = min(maxleft[i], maxright[i])
res += water - height[i]

return res

thank you, i understood this

I know it doesn't end up mattering but a piece of feedback I thought I'd give on the video, the order in which you explain in the drawing is:

1. Move the pointer
2. Calculate Volume
3. Update the leftMax

but in the actual code, you:

1. Move the pointer
2. update the max
3. Calculate the volume


I understand that this doesn't end up mattering in the end, however it can make it really confusing if you can't figure out why that's fine.

I don't think `if not height: return 0` is needed unless `height` could be `None`? (not allowed on the LC version)

This is the first hard problem I have ever solved! Although I only got the O(n)/O(n) solution (I used linear extra space for the "left" side), not O(1) space. I knew it must be possible with two pointers since I did Container With Most Water, I just couldn't quite get the logic correct.

Seems like someone vandalised needcode's github solution for this question.

Goodness, this problem was hell for me to visualise. I gave up on it when doing it on my own after a couple of hours because I couldn't come up with anything and I couldn't understand any of the solutions and their explanations. In particular I really didn't understand how you didn't need O(n) to figure out the required filling in a given space even if we ignored one side or the other. I had to go through your position-by-position explanation twice and I needed to make an array for all 5 calculations just to understand how to process the idea correctly, but at least it's how I got my breakthrough, and figuring out the two pointer solution after that was trivial.

Thank you for the video. Looking up what people thought were the hardest problems on leetcode and seeing this very problem get the most mentions made me feel a lot better about myself.

I don't know why I feel like line 14 should have been before line 13 according to his explanation, his solution still works. Because in that case we could be updating leftMax with height[l] without knowing if righMax is greater than height[l] or not. I am confused.

Update (I think I got it):

According to the way I am suggesting, we will have to check for negative values which his solution cleverly eliminates.

I wish I would udnerstand why can we safely assume that the right max doesnt matter in case we moved left pointer due to l < r.

Why is it l < r over l<= r?

Bro you are a life saver.

The O(1) solution is easiest understood if you imagine you only see what you have scanned from the pointers and building an image of the scenery progressively, imagine you are the computer and you are scanning the image from both left and right sides you know that the height of left is 1 and the height of right is 0 that means that you are looking at a slope starting from left to right and you cannot tell if there is any water in the next tile so what you do you shift right pointer you detect a height of 1 now the image that you see is sort of a long "lake" with height 1 and as the algorithm progresses you start drawing the image and the altitudes

"roughly 4 units" -- it's exactly 4 units LOL

‘…and it’s actually pretty simple…’ Excuse me while I throw my laptop across the room.

You are amazing mate !!!! I cant thankyou enough. Crisp, easy and efficient solutions.

I can't see any possible way for a human being to come up with this solution...

Just solved this problem with the O(1) solution and it took me 10 minutes to come up with. All thanks to NeetCode 150.

I started Neetcode 150 about 4 days ago and it becomes more and more clear how good the order of this list is. If I didn't solve "Container With Most Water" (the prior problem on the list), coming up with the solution for this problem could easily have taken me 30+ minutes to come up with, if at all.

This was my first hard difficulty question, feels so good to have solved it.

Thank you so much!

I've seen most of your videos.Great job explaining stuff. Can you post a solution/explanation for the infamous candy problem please?

great explanation like always! i wrote a long function to get this to work but your way was way better than mine glad i always watch your videos after im done to see a better way of doing the question

Instead of updating the maxLeft after you compare it, you can update it first so the subtraction will always be greater than or equal to 0. So you can always append the answer of "sum += leftMax - height[L]"

after your explaination iactually coded it myseld love you bro

i am too dumb to come up with an optimal approach, unless I have sen such trick before

Thanks!

sharing my solution that does the first approach by calculating maxL and maxR. O(n) time and O(n) space.

class Solution:
def trap(self, height: List[int]) -> int:
# at each height i
# the amount of water that can be trapped
# is equal to
# min(max_left_height, max_right_height) - height[i]

current_left_max = 0
max_left = [0] * len(height)
for i in range(len(height)):
if i > 0:
current_left_max = max(current_left_max, height[i - 1])
max_left[i] = current_left_max

current_right_max = 0
max_right = [0] * len(height)
for i in range(len(height) - 1, -1, -1):
if i < len(height) - 1:
current_right_max = max(current_right_max, height[i + 1])
max_right[i] = current_right_max

trapped_water = 0
for i in range(len(height)):
water_at_i = min(max_left[i], max_right[i]) - height[i]
trapped_water += max(water_at_i, 0)

return trapped_water

the way u make prolems easier drive m crazy thanks a lot plz don't stop

understood

you make it so simple, great job

The two pointer solution is insane, I would never come up with that 'on the spot' at an interview.

Actual best, most efficient explanation!!

this was amazing, proud of your videos NC, keep up the good work.

I don't even code in Python but I love your explanations, hence a subscriber.

Beautiful explanation

Thank you very much sir

Great Explaination !!!

dude you are a legend

Can anyone point me to any other video explaining the two pointer approach better ?

In your two pointer approach, are you sure it is correct to say that you do not need the true max_right value since we want the min(max_left, max_right)? For example, imagine we are at index one of some height array. On the left (at index 0) is the value 4, so the max_left at index 1 is 4. At the far right (index len(height) - 1) is the value 1. You would have it that the max_right is 1. But let's say at some position in between, but not including, index 1 and index Len(height) - 1 that there is a value 2. This would mean the true max_right is 2. The true min(max_left, max_right) calculation should yield 2. But yours would yield 1. Let's say the height at index 1 is 0. Then your water calculation at index 1 would be 1, when the actual water calculation should be 2. Does the reason that your two pointer approach works have to do with how you move the pointers? Does this somehow avoid this incorrect calculation? I can almost feel intuitively that this is so, but cannot explicitly reason it out at this point. Thanks for your time and great job on your videos!

Thanks a lot, I love to learn from your videos!

Amazing!

Thanks bro you are true gigachad

this is the most convoluted and horrible explanation of this problem that i've ever seen.

Thank you my dear FRIEND

Awesome as always! Unfortunately my solution got a TLE on one of the last test cases. Instead of checking maximum number of water by y axis like you do in your video, I was checking by x axis.

I really love your videos, please keep going on~

beautiful explanation. thanks