This was a great explanation. I did not even think about treating each index as an individual column of water. I was traversing the array to look for valleys, which made the code much more complicated.
Thanks for the great explanation. Although this is not a two pointer solution, your explanation helped me understand the intuition behind how a two pointer solution works; the one that dynamically keeps track of the left and right max value. Your videos are great, keep them coming!
These videos that end with "there's a more efficient method but it's pretty complicated" I would love to see a separate video anyway to describe it. Heck, a whole playlist of "the harder way" videos. Or at least a Wikipedia link in the description describing the harder, more efficient algorithm.
class Solution: def trap(self, height: List[int]) -> int: n = len(height) max_L = float('-inf') max_R = float('-inf') L = 0 R = n - 1 count = 0 if n == 0 or n == 1: return 0 while L
Master Data Structures & Algorithms For FREE at AlgoMap.io!
Everytime he said this problem is hard, I felt relieved.
Hey Greg FYI the more I have been watching your videos for a few weeks now and I can say you're a genuis.
Lololol thank you!!
This was a great explanation. I did not even think about treating each index as an individual column of water. I was traversing the array to look for valleys, which made the code much more complicated.
Actually Greg is beyond all of my college professors.
Awe haha
Thanks for the great explanation. Although this is not a two pointer solution, your explanation helped me understand the intuition behind how a two pointer solution works; the one that dynamically keeps track of the left and right max value. Your videos are great, keep them coming!
Thanks for explaining this problem in such an easy way!
Glad to hear it 😊
Great explanation, you made this hard problem really easy to understand
Oh I'm really happy to hear that
These videos that end with "there's a more efficient method but it's pretty complicated" I would love to see a separate video anyway to describe it. Heck, a whole playlist of "the harder way" videos. Or at least a Wikipedia link in the description describing the harder, more efficient algorithm.
Sorry about that!!
Listened to 17 seconds of video and subscribed the channel. He seems like a sane person who understands its a stupid question anyways 🤣
Thanks for the wonderful explaination
Great Explanation !! keep it up
awesome visualization! would love to see the O(1) space solution too.
Love the way you explain
heyy man! great work, i love you!!!
very nice explanation! cheers
if you were not going to show 2 pointers then why did you have it in the title.
Seems like you should take "2 Pointers" out of the video title.
Nah, that's the name of the algorithm
@@GregHogg No, this is a 1 pointer solution. The solution you allude to at the end of the video is a 2 pointer solution.
this is not 2 pointers approach - this is DP
why is the title 2 pointer if its not the solution of it?
Thank man, it is really helpful keep up the Good work. ☺
Thank you for saying it's stupidity hard 😂😂
With the trick, not so bad. Without the trick....
thanks man
My pleasure, thank you so much for your support!
This is not an optimal solution, and you are misguiding
this was not two pointers technically
it's good solution, but it's not "2 pointers", it's DP
Test case failed
height =
[0,1,0,2,1,0,1,3,2,1,2,1]
Output - 11
Expected = 6
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
l_wall = r_wall= 0
n = len(height)
max_left = [0] * n
max_right = [0] * n
for i in range(n):
j = -i-1
max_left[i] = l_wall
max_right[i] = r_wall
l_wall = max(l_wall, height[i])
r_wall = max(r_wall, height[j])
summ = 0
for i in range(n):
pot = min(max_left[i] , max_right[i])
summ += max(0, pot - height[i])
return summ
Insanely hard? literally an easy problem.
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
max_L = float('-inf')
max_R = float('-inf')
L = 0
R = n - 1
count = 0
if n == 0 or n == 1:
return 0
while L
This is not the best solution, and it's not a two-pointer approach either!!
I hate this silly question!!!