3186. Maximum Total Damage With Spell Casting | DP + Binary Search | Same as LIS

In this video, I'll talk about how to solve Leetcode 3186. Maximum Total Damage With Spell Casting | DP | Same as LIS
Let's Connect:
📱Discord (Join Community) : / discord
📝Linkedin: / aryan-mittal-0077
📸 Instagram: / codewitharyanbhai
💻 Twitter - / aryan_mittal007
🤖 Github: github.com/ary...
About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)
✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms

[@ARYANMITTAL]

How to balance College & CP - ruclips.net/video/79rxV2d86ww/видео.html

[@ashutoshpatel2050]

Bro it would be very helpful if u attach a submission link of the problem in the description.

[@krishpoptani7862]

I messed up thinking that dp for LIS works in O(N^2) and it will not work, and thought it should be a greedy problem.

[@saurabhchamoli5204]

Same....

[@pwjikashishya8883]

Why memoization gives TLE here(Although its Time Complexity is also N logN ).Can anyone explain

[@rev_krakken70]

I did binary search with memoization and it worked nicely.. didnt have idea it would be lis

[@MaheshKumar-mh9mj]

can u please share link to that code you submitted

[@aryamanagarwal1977]

In this question memoising the recursive solution gave TLE but ideally it should have passed

[@bhupendratiwari1564]

tried with that could pass test case 533 just used knap sack concvept class Solution {
public:
bool possible(int p,int check)
{
if(p==check-1 || p==check+1 || p==check+2 || p==check-2)
{
return false;
}
return true;
}
long long maximumTotalDamage(vector& power) {
sort(power.begin(), power.end());
int maxValue = *max_element(power.begin(), power.end());
long long pow=maxValue+3;
vectordp(maxValue + 4, 0);
for(int i=1;i=0;j--)
{
if (possible(power[i-1], j)) {
dp[j]= max(dp[j],power[i-1] + dp[power[i-1]]);
}
}
}

return dp[pow];
}
};

[@keerthivasan6107]

I solved without binary search by computing frequency first, then removing duplicates from array and then for each value, creating a 2d DP with 1. not taking it, 2. taking dp of previous value that is lesser than val - 2 by using a while loop and lowering pointer at max will only execute 3 times for each value + current value * freq. This got accepted.

[@Dota2Vibes]

I now wait for you video after every contest. Great work and nice balloons xD

[@udaymourya7322]

This problem was something like House Robber problem ❤

[@Virtualexist]

Sir k upar s gaya. 😢😢😢

[@devkumaracharyaiitbombay5341]

0:10 where is this channel i am not able to find it can somebody help to figure out this channel

[@saurabhchamoli5204]

Can we do this without using map
Just by sorting and applying the concept of lis

[@YashSharma-qs1ph]

class Solution {
public long maximumTotalDamage(int[] power) {
return f(0,new HashMap(),power);
}
public long f(int i,Map map,int p[])
{
if(i>=p.length)
return 0;
long nottake=f(i+1,map,p);
long contain=0,max=0,take=0;
if(map.containsKey(p[i]))
take=0+f(i+1,map,p);
else{
map.put(p[i]-2,1);
map.put(p[i]-1,1);
map.put(p[i]+2,1);
map.put(p[i]+1,1);
take=p[i]+f(i+1,map,p);
map.remove(p[i]-2);
map.remove(p[i]-1);
map.remove(p[i]+2);
map.remove(p[i]+1);
}
max=Math.max(take,nottake);
return max;
}
} can we do this question like this logic is simple values which we cant take store in map so that after going forward we cant take that value

[@jeetdesaimusic]

You have amazing logic building skills!

[@panchalvicky]

"Maqsad nhi bhulna hai" is permanent

[@namangupta-ko7kv]

class Solution {
public:
long long solve(vector& power, int i, unordered_map&mp, vector&dp){
if(i >= power.size())return 0;
if(dp[i] != INT_MIN) return dp[i];
long long include =0;
if(mp[power[i]-2] == 0 && mp[power[i]-1] == 0 && mp[power[i]+1] == 0 && mp[power[i]+2] == 0){
mp[power[i]]++;
include = power[i] + solve(power,i+1,mp,dp);
}
long long exclude = solve(power,i+1,mp,dp);
return dp[i] = max(include,exclude);
}
long long maximumTotalDamage(vector& power) {
unordered_mapmp;
sort(power.begin(),power.end());
int n= power.size();
vectordp(n,INT_MIN);
return solve(power,0,mp,dp);
}
};
Can anyone tell the problem in this code

[@jaypatel-rm8sc]

i did almost same ... did u find any error?
@ARYANMITTAL can u pls check

[@theexplorer9012]

tle?

[@jaypatel-rm8sc]

@@theexplorer9012 yes did u resolve ?

[@ss-xh3hf]

Great one

[@shreyash184]

Looks like now this code is not submitting it is failing for one test case !!

[@shreyash184]

long long maximumTotalDamage(vector& power) {
long long n = power.size();
map freq;
for(auto p : power){
freq[p]++;
}
unordered_map dp;
long long ans = 0, prevEl = 0, backEl = 0;
for(auto [el, fr] : freq){
auto backIt = freq.lower_bound(el - 2);
if(backIt != freq.begin()){
backEl = (*(--backIt)).first;
}
dp[el] = max(prevEl, el * fr + dp[backEl]);
ans = max(ans, dp[el]);
prevEl = el;
}
return ans;
} This is same code butnow it is failing for 1 test case, @aryan can please check once

[@ARYANMITTAL]

Bro dp[el] = max( dp[prevEl] , …….) 🌚

[@ayushmishra1207]

@@ARYANMITTAL and fun fact 497 test case are being passed 😂😂 even after this blunder leetcode test case 🍵

[@mayankparmar4321]

@@shreyash184 we can also remove (ans = max(ans, dp[el]);) line and just return dp[prevEl] for further optimization

[@a3rdtierguy864]

2nd question please bhaiya

[@ARYANMITTAL]

Coming in 15min sir❤

[@a3rdtierguy864]

@@ARYANMITTAL bhaiya by memoization able to passed 537 testcases but got mle in every contest i write the recursive but at last got tle due to few missed cases.

[@theexplorer9012]

@@ARYANMITTAL please saar

[@Engineering.Wallah]

Blue shirt is permanent