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.
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!
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
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.
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'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.
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])
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%
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.
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.
small nitpick on 10:25 dp[2] is 7 not 8
🤓
This it tough with that double DP aspect to it, feels like a Hard problem IMO. Thanks for the awesome explanation as always man
this dp monster seems to have no bounds to its power😢😢
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.
we nesting dp now
10:22 Should be 1+max(6,4)=7
Genius solution as always😮
wow. didn't know that solution so simple! incredible!
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
This is the first video of neetcode where I am unable to understand what he is explaining
it would have been be good if you could share your thought process/intuition.
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!
Damn, looked at various solutions, but yours is very easy to understand
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
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
Beautiful explanation. Thank you
very smart technique
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.
Thanks for the consistent videos mate.!❤I appreciate your efforts
Thanks for this video. This will be my first time solving DP problem.
☠
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.
thank you for sharing this!
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
Thanks, great explanation.
I am here just to hear the description read out :)
very nice explanation
you using a new keyboard or what, a lot of typos today :D, keep up the good work though!
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
this problem is not medium difficult, it is hard
looking for you
why you are add 1 with value at 2:10
Because the value at that cell is 1
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.
Can you say your intuition about it
why the hell would anyone ask this in an interview bruv😭
Honestly a pretty simple dp problem
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 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%
isn't it like nqueens problem a pattern like that
🤯🤯
The video is all about here and that.hahaha
If i hadn't done dp can i solve
no
Yes, just do it
I am tired boss :(
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.
what a problem.
Nah the explanation wasn't it, after the duplicates thingie came in
i got lost after that