Leetcode 1937 Maximum Number of Points with Cost

Third problem from Leetcode Weekly Contest 250
Problem Links :
Leetcode 1937 : leetcode.com/problems/maximum...
Leetcode 1014 : leetcode.com/problems/best-si...
Leetcode 931 : leetcode.com/problems/minimum...
Contest Link :
leetcode.com/contest/weekly-c...
Solution Links :
Leetcode 1937 : github.com/Sandip-Jana/Youtub...
Leetcode 1014 : github.com/Sandip-Jana/Youtub...
Leetcode 931 : github.com/Sandip-Jana/Youtub...
Explanation : github.com/Sandip-Jana/Youtub...
Hope you learned something from this video. Do not forget to like and subscribe this channel :)
#Sandip Jana
#sandip jana
#sandip_jana
#Leetcode
#weekly contest 250

[@auto8ot644]

I really like how you explained the question using Leetcode 931 and 1014 as support to explain 1937. Thanks for the video!

[@sandip_jana]

Glad it was helpful!

[@rohithkumargattu6749]

Thank you so much! It is a great explanation, sir, definitely I am gonna share this video and channel with all my friends to watch, it is really helpful. please solve the problems consistently, definitely, it will help lots of people and this channel definitely gonna rock

[@nurshuvo3854]

Thanks man. I like the way you explained.

[@user-zi1sr6uc7b]

Nice Explanation, thanks

[@motivation_hubPJ]

Very nice explanation thanks a lot !

[@mitasingh1553]

if it is abs diff. then it will always return a positive value then why j< k or j>k matters?

[@aviralarpan7350]

Thanks a lot

[@harshalgarg1149]

Thanks a lot.

[@srndrpec]

one shot, three problems...good approach

[@cyrusthapa794]

Too Great ! XD

[@ujjvalsharma5055]

great explanation. Keep up with the good work

[@nipunaggarwal7568]

Sir, amazing explanation

[@rupayanghosh150]

Great explanation

[@ShivangiSingh-wc3gk]

Great Explanation, thank you

[@sandip_jana]

Your welcome :)

[@vamshisagargadde1629]

very good explanation.

[@paragroy5359]

Nice explanation.........thanks for the video...

[@shayranadilse1005]

You are op🎉🎉

[@ankurshah3112]

Very good explanation. Thank you

[@sandip_jana]

Welcome

[@Adrian-xe2sn]

Could you potentially explain how you got case 2 : -j < k? Like why is it -j?

[@sandip_jana]

No No. I wrote it as
Case 2 :- j < k
Its not -j haha sorry for the trouble :)

[@souravadhikari7485]

Can you please explain
rightMax[m-1] = dp[i-1][m-1] - (m-1);
Why do we take -(m+1) part in your code?

[@sandip_jana]

Its simple :
the state is :
--> dp[i-1][k] - k
so when k == m-1
we will have
--> dp[i-1][m-1] - (m-1)
we simply replace k with m-1. because the last column is denoted by m-1

[@AnkitKumar-po4wx]

nice explanation

[@chetansahu1505]

@3:50 I stopped the video here and went to solve leetcode 931 (nicely done in one go) and leetcode 1014 as well (realized I solved it earlier). I got some ideas to handle now 1937 but still in a little muddle.

[@sandip_jana]

Ok thanks for feedback. So where exactly do you have doubts? Which part of the problem you didn't understand?

[@blasttrash]

@@sandip_jana link not working

[@sandip_jana]

Hi. Yes it wont work. let me know if you have any specific doubts. i will try to answer them here

[@sandip_jana]

github.com/Sandip-Jana/CZcams/blob/main/MaximumNumberOfPointsWithCost.txt

[@nribackpacker]

very good explanation appreciated

[@sandip_jana]

Glad it was helpful!

[@yhdzhang]

Thanks. Really good explanation. My question is how am I meant to come up with these math equations if I haven't seen the question before

[@sandip_jana]

Good question! Actually this comes with practice . the more problems we solve the better we become

[@dsacp7570]

today i solved sightseeing one, got stuck in contest though for this.

[@TheIndianChroniclee]

Very Nice Explaination ..

[@sandip_jana]

Thanks and welcome

[@ShivangiSingh-wc3gk]

Such a great way to tackle DP write mathematical equations and then break it apart.

[@chetansahu1505]

Many people like me come on CZcams, post leetcode contest to help themselves upsolve the unsolved problems. So if you could make videos of all 4 problems after every contest that would be of great help. Thanks brother for such a great explanation.

[@sandip_jana]

I will try. I am still struggling to explain properly in my videos as evident from the bloopers :D . But yeah i will try :)

[@gururajchadaga]

what about the case j == k?

[@muraliKrishnaanimi]

it will be 0 anyways. so penalty will be 0

[@ShivangiSingh-wc3gk]

Came back to it in the morning, I am still failing to understand that how it is O(nm)

[@ShivangiSingh-wc3gk]

Don't we have to do all the values of k

[@sandip_jana]

Correct we have to do it for all values of k. and what does k signify??
Case 1 : j > k
so k = ( 0,1,.... j-2 , j-1 )
Case 2 : j < k
so k = ( j+1 , j+2 ..... m-1 )
So k is the number of columns we have.
So for each row we simply precompute the leftPrefixMaximum for all values of `k`.
And the rightSuffixmaximum for all values of `k`.
Finally we calculate the best answer for all current row.
Hence time complexity = O( n * ( m + m + m ) ) ~ O ( n*m )
Let me know if you have any doubts
Solution for reference : github.com/Sandip-Jana/CZcams/blob/main/Leetcode1937.java

[@vardhanyash243]

noice

[@RG-yj4cb]

todu ho bhai, 15 min teen questions chaap diye!

[@sandip_jana]

thanks :)

[@ishaankaustav727]

💚💚

[@HarendraKumar-hl8nh]

Sir, Please upload beautiful problems on Dp and please continue teaching on white board. 🙏🙂 I am eagerly waiting... for your upcoming videos on Dp.

[@BRBallin1]

Sorry but I didn't understand the problem still based on your explanation. It focused too much on the notations but should've done a walkthrough with the logic directly per iteration

[@sandip_jana]

No worries. I am trying to explain in a better way

[@shaikhkamran532]

best of what? when you explain explain it clearly please

[@sandip_jana]

I am trying to improve my explanation. You may try to read other explanations in the discussion forum of problem for better idea. Hope that helps.

[@ankitmishra399]

hey can u optimize memiozed approach code attach below

[@ankitmishra399]

class Solution {
Long dp[][];
public long maxPoints(int[][] mat) {
long max=0;
dp=new Long[mat.length][mat[0].length];
for(int j=0;j