Memoization gave me TLE on 144th testcase and simple DP gave TLE on 153rd testcase. I was confident of solving this myself but this problem humbled me. The optimization is so smart!
My intuition for the left/right optimization: Let's say the previous row is [A, B, C, D]. We only consider elements from left-to-right for now. The maximum value for the first element in the current row is: max(A) == A The maximum value for the second element in the current row is: max(A - 1, B) == max(A- 1, B) The maximum value for the third element in the current row is: max(A - 2, B - 1, C) == max(max(A - 1, B) - 1, C) The maximum value for the forth element in the current row is: max(A - 3, B - 2, C - 1, D) == max(max(max(A - 1, B) - 1, C) - 1, D) So it's a rolling max(prev_max - 1, element_right_above). And similarly do right-to-left for the second half.
Probably not, but now when you get to a similar problem you'll know how to solve and that's what matter. What we can get from this problem is the idea from left- right and that some problems have double nested dp
It's a bit of a stretch to call the solution DP. It's more of a clever precalculation. The features of the solution lacks the usual features of DP like exploring combinations. I get that is encoded in the precalculation hence why I think it shouldn't be tagged as dynamic programming.
i knew it was a DP problem the second I read the problem and constraints but I really got humbled when Memoization failed, tried fixing it but did not work, came straight here, Thanks neetcode!
Thank you for such a great explanation. ❤ I couldnt able to identify that this can be solved using dp 😢 How to identity dp can be used to problems I used different approach (i think its greedy) but it was wrong, my solution is.. taking max val in a row and keeping track of max id and using this to find max val in next row and summing up.. got failed bcoz elements in a row are not always unique.
I'm not sure if my take is correct, but here's how i understood it, left and right feels like a greedy solution more than a dp solution where you take the max between the previous and current utility (val - cost) where the current col has a cost of 0 and the relative cost is the dist from the current col, this is because you cant really reuse the calculations for any of the cols because each cols despite having the same utility have a relative cost
Let's say the previous row is [A, B, C, D]. We only consider elements from left to right for now. The maximum value for the first element in the current row is: max(A) == A The maximum value for the second element in the current row is: max(A - 1, B) == max(A- 1, B) The maximum value for the third element in the current row is: max(A - 2, B - 1, C) == max(max(A - 1, B) - 1, C) The maximum value for the forth element in the current row is: max(A - 3, B - 2, C - 1, D) == max(max(max(A - 1, B) - 1, C) - 1, D) So it's rolling max(prev_max - 1, element right above). And similarly do right to left for the second half.
This kind of problems is the problems where if your mind don't randomly send a hint you just can't rationalize until a solution, but with enough practice, you can increase the chance of the mind sending a hint but it's always not 100%
For the life of me, I cant figure it out how to optimize the get max from previous row part. Thank you so much for the explaination. 2 questions though: - At which point does the thought of 6:00 occurred to you that it is impossible? Did it come at you intuitively or you somehow proved it using quick maff? I too thought that it is impossible at first, but the thought of looping all cells in the prev rows to pick one was too "bruteforce" and I thought it would result in TLE, so I discarded that thoughts. - How would you know that looping each row twice (thrice to build the actual dp) would not result in TLE? I did come up with the thoughts of check max for each current_element but the thought of looping all the rows made me discarded that approach
i figured out another approach using heaps, which is slower (2460ms), but still passed. Time complexity mlogm * n. class Solution: def maxPoints(self, points: List[List[int]]) -> int: height = len(points) width = len(points[0]) ans = [[0] * width] + [[None] * width for _ in range(height)] for r in range(height): heap = [(-points[r][i] + ans[r][i], i) for i in range(width)] heapq.heapify(heap) while heap: n, i = heapq.heappop(heap) if ans[r+1][i] is None: ans[r+1][i] = n if i > 0 and ans[r+1][i-1] is None: heapq.heappush(heap, (n+1, i-1)) if i < width -1 and ans[r+1][i+1] is None: heapq.heappush(heap, (n+1, i+1)) return -min(ans[-1])
at this point leetcode is testing my willpower rather than my coding knowledge
Agree
The idea for optimizing from O(m*n^2) to O(m*n) is so smart....
Memoization gave me TLE on 144th testcase and simple DP gave TLE on 153rd testcase. I was confident of solving this myself but this problem humbled me. The optimization is so smart!
At this point its not dynamic programming anymore, its double penetration
My intuition for the left/right optimization:
Let's say the previous row is [A, B, C, D].
We only consider elements from left-to-right for now.
The maximum value for the first element in the current row is: max(A) == A
The maximum value for the second element in the current row is: max(A - 1, B) == max(A- 1, B)
The maximum value for the third element in the current row is: max(A - 2, B - 1, C) == max(max(A - 1, B) - 1, C)
The maximum value for the forth element in the current row is: max(A - 3, B - 2, C - 1, D) == max(max(max(A - 1, B) - 1, C) - 1, D)
So it's a rolling max(prev_max - 1, element_right_above).
And similarly do right-to-left for the second half.
small nitpick on 10:25 dp[2] is 7 not 8
🤓
this dp monster seems to have no bounds to its power😢😢
This it tough with that double DP aspect to it, feels like a Hard problem IMO. Thanks for the awesome explanation as always man
Genius solution as always😮
Everything up to left/right was quite intuitive. I understand what you did and why. I don't understand the intuition. That's the frustrating part.
took a two week break and came back to this never quitting lc again :( skill gapped
I've been doing leetcode and I still can't reason this shit.
@@leshius7230deadass, feels like i got hit with the men in black flash
wow. didn't know that solution so simple! incredible!
we nesting dp now
10:22 Should be 1+max(6,4)=7
Damn, looked at various solutions, but yours is very easy to understand
How do u come out with this? Is it try and error ? Or just experience , cause i would never would have think of computing it left and right.
will solving enough dp problems help me come up with the left and right array intuitively? I was able to do the brute force dp but not thsi one
NO😑
Probably not, but now when you get to a similar problem you'll know how to solve and that's what matter. What we can get from this problem is the idea from left- right and that some problems have double nested dp
it would have been be good if you could share your thought process/intuition.
It's a bit of a stretch to call the solution DP. It's more of a clever precalculation. The features of the solution lacks the usual features of DP like exploring combinations. I get that is encoded in the precalculation hence why I think it shouldn't be tagged as dynamic programming.
very smart technique
Thanks for the consistent videos mate.!❤I appreciate your efforts
i knew it was a DP problem the second I read the problem and constraints but I really got humbled when Memoization failed, tried fixing it but did not work, came straight here, Thanks neetcode!
Beautiful explanation. Thank you
thank you for sharing this!
Thanks, great explanation.
Memoization solution gave me the tle is horryfying.
How much testcases u passed with memoization?
I got TLE on 144th testcase
@@069_Souvik same
@@069_Souvik same
@@069_Souvik i got stuck in this too
@@069_Souvik 152
Thank you for such a great explanation. ❤
I couldnt able to identify that this can be solved using dp 😢
How to identity dp can be used to problems
I used different approach (i think its greedy) but it was wrong, my solution is.. taking max val in a row and keeping track of max id and using this to find max val in next row and summing up.. got failed bcoz elements in a row are not always unique.
Thanks for this video. This will be my first time solving DP problem.
☠
very nice explanation
This is the first video of neetcode where I am unable to understand what he is explaining
The fact I can't get such intuition on the spot makes me hopeless for interviews
do such people normally exist?
@@LifeZone-j3w well Neetcode is one 😅, and probably many more
you using a new keyboard or what, a lot of typos today :D, keep up the good work though!
I am here just to hear the description read out :)
Leetcode's difficulty algorithm is broken! No way this is a Medium and not a Hard.
Can you say your intuition about it
can anyone explain me how left and right arrays work to give us the max value? I am unable to understand how its working.
I'm not sure if my take is correct, but here's how i understood it,
left and right feels like a greedy solution more than a dp solution where you take the max between the previous and current utility (val - cost) where the current col has a cost of 0 and the relative cost is the dist from the current col, this is because you cant really reuse the calculations for any of the cols because each cols despite having the same utility have a relative cost
@@Elias_90 thanks bro
Let's say the previous row is [A, B, C, D].
We only consider elements from left to right for now.
The maximum value for the first element in the current row is: max(A) == A
The maximum value for the second element in the current row is: max(A - 1, B) == max(A- 1, B)
The maximum value for the third element in the current row is: max(A - 2, B - 1, C) == max(max(A - 1, B) - 1, C)
The maximum value for the forth element in the current row is: max(A - 3, B - 2, C - 1, D) == max(max(max(A - 1, B) - 1, C) - 1, D)
So it's rolling max(prev_max - 1, element right above).
And similarly do right to left for the second half.
At this point i think i should just give up
keep grinding and it will be worth it
This kind of problems is the problems where if your mind don't randomly send a hint you just can't rationalize until a solution, but with enough practice, you can increase the chance of the mind sending a hint but it's always not 100%
this problem is not medium difficult, it is hard
why the hell would anyone ask this in an interview bruv😭
Honestly a pretty simple dp problem
isn't it like nqueens problem a pattern like that
🤯🤯
looking for you
I always feel like I am improving until I get a DP question... Is this really a medium? :(
Its ok, its a hard in disguised
Leetcode's difficulty algorithm is broken! No way this is a Medium and not a Hard.
For the life of me, I cant figure it out how to optimize the get max from previous row part. Thank you so much for the explaination.
2 questions though:
- At which point does the thought of 6:00 occurred to you that it is impossible? Did it come at you intuitively or you somehow proved it using quick maff? I too thought that it is impossible at first, but the thought of looping all cells in the prev rows to pick one was too "bruteforce" and I thought it would result in TLE, so I discarded that thoughts.
- How would you know that looping each row twice (thrice to build the actual dp) would not result in TLE? I did come up with the thoughts of check max for each current_element but the thought of looping all the rows made me discarded that approach
why you are add 1 with value at 2:10
Because the value at that cell is 1
If i hadn't done dp can i solve
no
Yes, just do it
what a problem.
The video is all about here and that.hahaha
I am tired boss :(
Nah the explanation wasn't it, after the duplicates thingie came in
i got lost after that
i figured out another approach using heaps, which is slower (2460ms), but still passed. Time complexity mlogm * n.
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
height = len(points)
width = len(points[0])
ans = [[0] * width] + [[None] * width for _ in range(height)]
for r in range(height):
heap = [(-points[r][i] + ans[r][i], i) for i in range(width)]
heapq.heapify(heap)
while heap:
n, i = heapq.heappop(heap)
if ans[r+1][i] is None:
ans[r+1][i] = n
if i > 0 and ans[r+1][i-1] is None:
heapq.heappush(heap, (n+1, i-1))
if i < width -1 and ans[r+1][i+1] is None:
heapq.heappush(heap, (n+1, i+1))
return -min(ans[-1])