Maximum Subsequence Score | Intuition | AMAZON | Leetcode-2542 | Explanation ➕ Live Coding
Vložit
- čas přidán 23. 05. 2023
- Hi everyone, this is the 8th video of our Heap Playlist.
In this video we will try to solve a very good Problem on the heap “Maximum Subsequence Score”.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Maximum Subsequence Score
Company Tags : AMAZON
My solutions on Github : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/maximum...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish
deekho bhai log mere dimag main pheli cheez dp aayi aur tle aaya without second thought mai codestory withmik ke paas aaya 40 min ka video dekha mai samajh gya mik will explain the recurrsion aur he did
i think aagar sayad mik 2 saal phele start krta content dalna i would have been more better
there is saying that "you get the right teacher only when you have worked enough hard to find one"
and every subscriber of mik has worked hard to get him
Satyam, you made my day ❤️🙏
Thank you so much.
Pinning this comment so that I can find and read it whenever i want ❤️❤️❤️
@@codestorywithMIK thank you sir I feel blessed to learn from u
Wo saying ek number h bhai🔥🔥
@satyamkumaryadav1560 dil ki bat boldi😢
wow
You are the best teacher on youtube buddy
Someone give this man an award
Bhai aap god ho
saari playlists kamal ki hai.....or explanation top notch
Also one important thing, in Recursion approach, we don't need to use priority queue. Instead, you can keep updating the min element during recursion only. Please find the code below :
//Recursion + Memo + Without min-heap
class Solution {
public:
int K;
int n;
unordered_map mp;
long long solve(vector& nums1, vector& nums2, int sum, int min_el, int i, int count) {
if(count == K) {
return sum * min_el;
}
if(i >= n) {
return 0;
}
string key = to_string(sum) + "_" + to_string(min_el) + "_" + to_string(i) + "_" + to_string(count);
if(mp.find(key) != mp.end())
return mp[key];
int min_now = min(min_el, nums2[i]);
long take_i = solve(nums1 , nums2 , sum + nums1[i] , min_now, i+1 , count+1);
long not_take_i = solve(nums1 , nums2 , sum, min_el, i+1 , count);
return mp[key] = max(take_i, not_take_i);
}
long long maxScore(vector& nums1, vector& nums2, int k) {
K = k;
n = nums1.size();
mp.clear();
return solve(nums1 , nums2 , 0 , INT_MAX , 0 , 0);
}
};
Your videos are the proof that you are a true programming expert😁😍. Thank you for sharing your expertise with us and helping us improve our skills.😊
Thank you so much ❤️❤️
Long video - Must Watch of this channel 😁.
This guy is simply a LEGEND. explained even minute details that I couldn't get from best channels on CZcams as well as neither from Leetcode official solution
adbhut
Finest explanation for this problem in the entire CZcams
amazing approach
The style of approaching every question, narration, and representation. Everything is so perfect, one of the best channels I have ever found for learning DSA! I have learned a lot from your videos, wish you keep growing!
Thanks a lot Harsh ❤️❤️❤️❤️
totally agree
programming feels addictive with you sir ! your explanations really motivates to learn more and more about coding .thank you so much .
Glad to hear that 🙏😇
G.O.A.T / L.E.G.E.N.D ❣
I stopped at 31:13 and coded it up with the story
I also thought of DP first.
couldn't come up with 2nd approach (optimal) on my own.
If I saw this guys video then my search is over that's all it's not a easy question at all but this guy made it easy for you ❤❤
It means a lot. Thank you for watching 🙏😇
what a beautiful explanation.
Glad it was helpful! 🙏❤️
thanks for the video
One is best explained. Becomes top in dsa
🙏😇❤️
Awesome explanation!
learn't something new Thank You...
Thanks a lot ❤️
The only Channel who goes to depth and even minute details
i appreciate your narration style for this question bro.... EXPLAINED VERY WELL! ❤❤
Broooooo, I was genuinely waiting for your video because I knew you'd definitely start from the basics(i.e., recursion). P.S.:- I went through a couple of other videos in the afternoon. So now, I can assure you that This is the best explanation!!!
Keep it up & Thank you so much.
Thanks a lot ❤️❤️
bro literally iam searching for best explination from hours..... and even since yesterday ...... iam fuckin lucky that you uploded this video today ...thankyou bhai love from telengana...You rocked with best explination bro love youuuuuuu
Thank you so much Karthik ❤️
thank you
Indeed a very nice question , learned the concept , thought a lot about how to use heap here but couldn't .
Indeed
@@codestorywithMIK Bhaiya thanks for the fantabulous explanation as always.🚀🔥
Thanks a lot Sunny ❤️❤️❤️
It's been a while I'm watching your videos to learn the logic from the very basic. Your explanation is really good. Keep the Hard work on .
Thank you so so much ❤️🙏
Love your videos bro! Keep up the good work!
Thank you so much Debasish ❤️❤️❤️
Excellent explanation bro, keep it up!
Thank you so much Girik ❤️❤️
❤
This was awesome loved your way of explaining with all the details. 👍🏻
Thanks a lot Vedraj ❤️❤️❤️
Thanks for such a crystal clear intuition
Thanks a lot for watching my video sanjeeb ❤️❤️❤️
bro, you're really good in explaination, loads of love to you bro , I did it with recursion earlier to your video, it failed like you said. I waited for your video for good aproach, really awesome, Thank You, I wiil surely recomend your channel, with new coders
Thank you so much
Means a lot Ravi ❤️❤️❤️
the question is good
Indeed. A fantastic one
Did the same thing instead of priority queue just took minimum at each call ☺
Even though here constraints are too high to memorize 😥
int n;
long long solve(vector& nums1, vector& nums2, int idx, int minN, int k, long long sum)
{
if(k == 0)
{
return sum * minN;
}
if(idx >= n)
{
return 0;
}
long long notTake = solve(nums1, nums2, idx+1, minN, k, sum);
sum += nums1[idx];
minN = min(minN, nums2[idx]);
long long take = solve(nums1, nums2, idx+1, minN, k-1, sum);
return max(take, notTake);
}
long long maxScore(vector& nums1, vector& nums2, int k) {
n = nums1.size();
return solve(nums1, nums2, 0, INT_MAX, k, 0);
}
So glad that you first tried brute force recursive approach. It’s very important for interviews to first try brute force.
in first approach , i think instead of creating a priority queue, we can check the minimum while calling the function like, min(mi,nums2[i]), where mi is minimum up until element of present index,this can improve space complexity
That’s correct.
Let me add that in the video captions
Added in the captions. Thanks a lot for mentioning this @Shashank.
class Solution {
public:
int K;
int n;
unordered_map mp;
long long solve(vector& nums1, vector& nums2, int sum, int min_el, int i, int count) {
if(count == K) {
return sum * min_el;
}
if(i >= n) {
return 0;
}
string key = to_string(sum) + "_" + to_string(min_el) + "_" + to_string(i) + "_" + to_string(count);
if(mp.find(key) != mp.end())
return mp[key];
int min_now = min(min_el, nums2[i]);
long take_i = solve(nums1 , nums2 , sum + nums1[i] , min_now, i+1 , count+1);
long not_take_i = solve(nums1 , nums2 , sum, min_el, i+1 , count);
return mp[key] = max(take_i, not_take_i);
}
long long maxScore(vector& nums1, vector& nums2, int k) {
K = k;
n = nums1.size();
mp.clear();
return solve(nums1 , nums2 , 0 , INT_MAX , 0 , 0);
}
};
@@codestorywithMIK thanks for the second solution, couldn't come up for it myself
Aap hamko dsa se pyar karwa ke hi rahoge ❤️❤️❤️❤️❤️
That’s the ultimate goal 😇🙏❤️
in recursion, instead of priority queue we can maintain a running minimum element
Indeed yes. ❤️❤️
sir waiting for todays questions
Being uploaded.
Sorry for the delay.
@@codestorywithMIK Thank you so much sir
It’s my pleasure ❤️❤️
For recursive approach we can keep track of min element instead of pq
Much easier, code below for reference.
public int ans = 0;
public long maxScore(int[] nums1, int[] nums2, int k) {
helper(0, 0, Integer.MAX_VALUE, nums1, nums2, k);
return ans;
}
public void helper(int idx, int sum, int min, int[] nums1, int[] nums2, int k) {
if (k == 0) {
ans = Math.max(ans, sum * min);
return;
}
if (idx == nums1.length) return;
helper(idx + 1, sum, min, nums1, nums2, k);
helper(idx + 1, sum + nums1[idx], Math.min(min, nums2[idx]), nums1, nums2, k - 1);
}
if possible pls add java code too
Hi Ayush.
Actually in every video @Abhijeet Singh posts the Java code in the comment section. You can see his comment.
.
And i will try to include java for sure
Thanks for your suggestion ❤️❤️
Recursive code without using PQ-
class Solution {
public:
//can't be memoized due to high constraints, also not an optimal solution for this question
int n;
long long recur(vector& nums1, vector& nums2, int k,int ind,int mini,long long total)
{
if(k == 0){
return ((long long)mini)*total;
}
if(ind >= n)return INT_MIN;
long long notpick = recur(nums1,nums2,k,ind+1,mini,total);
long long pick = recur(nums1,nums2,k-1,ind+1,min(mini,nums2[ind]),total+nums1[ind]);
return max(notpick,pick);
}
long long maxScore(vector& nums1, vector& nums2, int k) {
n = nums1.size();
return recur(nums1,nums2,k,0,INT_MAX,0);
}
};
How to become as expert as you?🥺Big fan vhai🙏
Just keep it consistent.
We all will grow together ❤️❤️❤️
@@codestorywithMIK vhai ak aur question tha.Hum jis ques me fash rahe hai woh aap ki video dekh k easy ho jata hai.but Is our skill growing?
Definitely your skill will grow
BUT, you MUST ensure three things :
1) You understand it thoroughly
2) You practice it again after some days
3) You solve some similar/related problems.
Hi guys, I tried to memoize this recursion approach using map. (Still got TLE)
class Solution {
public:
int K;
int n;
priority_queue pq;
unordered_map mp;
void removeNums2_i(int num) {
vector temp;
while(!pq.empty()) {
int x = pq.top();
pq.pop();
if(x == num) {
break;
}
temp.push_back(x);
}
for(int &x : temp) {
pq.push(x);
}
}
long long solve(vector& nums1, vector& nums2, int sum, int min, int i, int count) {
if(count == K) {
return sum * min;
}
if(i >= n) {
return 0;
}
string key = to_string(sum) + "_" + to_string(min) + "_" + to_string(i) + "_" + to_string(count);
if(mp.find(key) != mp.end())
return mp[key];
pq.push(nums2[i]);
long take_i = solve(nums1 , nums2 , sum + nums1[i] , pq.top(), i+1 , count+1);
removeNums2_i(nums2[i]);
long not_take_i = solve(nums1 , nums2 , sum, min, i+1 , count);
return mp[key] = max(take_i, not_take_i);
}
long long maxScore(vector& nums1, vector& nums2, int k) {
K = k;
n = nums1.size();
mp.clear();
return solve(nums1 , nums2 , 0 , 0 , 0 , 0);
}
};
Your way of memorization using strings hit me pretty hard 🤐, because I didn't think in that way😥, please teach us more and more about memorization techniques too 😅
I have started my DP concepts playlist. I will be teaching all these for sure ❤️❤️❤️
@@codestorywithMIK Waiting for that 🤗
Sure Vetla ❤️
Bhaiya
1. DP wale ki time complexity kya hogi?
2. Priority queue ki kya zaroorat padhi? Directly compare kr lete nums2[i] aur min wale argument ko.
Dry run this example
[2,1,14,12]
[11,7,13,6]
3
If we sort nums2 then both arrays become
[12,1,2,14]
[6,7,11,13]
Now suppose we take min ele 13 so from nums1 we have possibilities which 3 number to pick either 14, 2 ,1 or 14,2,12. Now to maximize our answer we will take second possibility in which we have replaced 1 with 12 . So to take max k ele we have to use priority queue(min heap) to remove min ele from top and add another greater ele
1. We have 2 possibility for every ith element (take_i and not_take_i) - which sums up to 2^ n possibilities
However, for every possibility, we push into priority queue, remove from priority_queue (which takes klog(k)) since priority_queue will have max k elements.
So, overall TC will go to O(2^n * klog(k))
2. @yuvhraj has given a very good example to answet that.
@@codestorywithMIK thank you sir ☺️
I really like your curiosity level @Xiao
And I am glad @yuvhraj is trying Dry run on examples . It’s the best way to overcome doubts
Yes, we need not consider priority queue.
Sir can you also code in Java.
Hi Rizwan.
Actually in every video @JJ posts the Java code in the comment section.
I am waiting for his comment. I will share here.
And i will try to include java for sure
Thanks for your suggestion ❤️❤️
Rizwan, added in the comment brother.. Sorry for the delay today.
Hi MIK, aaj ka Leetcode challange question daalne vale ho?
Hi Hiren,
Sorry for the delay, had been really occupied in office.
It will come today. Need some time brother
Thank You MIK 😊❤️
Dp ka hi intution hi aaya bas jab solve kar rha tha🥲
Same , mujhe memory limit exceeded aa gya
Knapsack wale tarike se kiya tha
@@tushargupta9137 Mujhe TLE aaya tha
@@xortixgaming655 kitna test case pass hua tha? Mera 12 me ruk gya tha
Exactly.
Java implementation:
Recursive TLE:
class Solution {
private int k;
private int n;
private int solve(int[] nums1, int[] nums2, int sum, int min, int idx, int count) {
if(count == k) {
return sum*min;
}
if(idx >= n){
return 0;
}
int curr_min = Math.min(nums2[idx],min);
int take = solve(nums1,nums2,sum+nums1[idx], curr_min, idx+1, count+1);
int notTake = solve(nums1,nums2,sum,min,idx+1,count);
return Math.max(take, notTake);
}
public long maxScore(int[] nums1, int[] nums2, int k) {
this.k = k;
this.n = nums1.length;
return solve(nums1,nums2,0,Integer.MAX_VALUE,0,0);
}
}
Greedy with PQ:
class Solution {
public long maxScore(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
int[][] combined = new int[n][2];
for(int i=0; i b[1]-a[1]);
PriorityQueue pq = new PriorityQueue(k);
long kSum=0;
for(int i=0; i
Thanks a lot JJ ❤️❤️❤️
It's not memoizable
I tried to memoize this using map. And also got rid of min_heap (Still got TLE)
class Solution {
public:
int K;
int n;
unordered_map mp;
long long solve(vector& nums1, vector& nums2, int sum, int min_el, int i, int count) {
if(count == K) {
return sum * min_el;
}
if(i >= n) {
return 0;
}
string key = to_string(sum) + "_" + to_string(min_el) + "_" + to_string(i) + "_" + to_string(count);
if(mp.find(key) != mp.end())
return mp[key];
int min_now = min(min_el, nums2[i]);
long take_i = solve(nums1 , nums2 , sum + nums1[i] , min_now, i+1 , count+1);
long not_take_i = solve(nums1 , nums2 , sum, min_el, i+1 , count);
return mp[key] = max(take_i, not_take_i);
}
long long maxScore(vector& nums1, vector& nums2, int k) {
K = k;
n = nums1.size();
mp.clear();
return solve(nums1 , nums2 , 0 , INT_MAX , 0 , 0);
}
};
U got tle simply because problem cant be broken into smaller problems which overlap
Indeed I realised this. Thanks
Small follow up for this problem: Consider subarray instead of subsequence. There will be a slight change in the approach
@codestorywithMIK , thanks for your solutions. I recently joined your channel, 1 month back and found your every video vey useful.
Just wanted to check with you for this recursion based solution I think there is no need to take priority_queue to check minimum value.
it can be updated easily on every processed element from nums2 as done below. What are your thoughts ?
//global variable
long long sum;
int minn;
long long res ;
void bt(vector& nums1, vector& nums2, int ind, int k, int count)
{
if(count >= k )
{
long long val = sum*minn;
res = max(res, val);
return;
}
if(ind==n)
return;
sum = sum + nums1[ind];
int earlier_min = minn;//minn is global variable
minn = min(minn, nums2[ind]);
bt(nums1, nums2, ind+1, k, count+1);
minn = earlier_min;
sum = sum -nums1[ind];
bt(nums1, nums2, ind+1, k, count);
}
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize ("O3,unroll-loops")
class Solution {
public:
priority_queue pq;
long long solve(vector &nums1, vector& nums2, long long sum, int mini, int idx, int count, int k, int n){
if(count == k){
return sum*mini;
}
if(idx >= n){
return 0;
}
pq.push(nums2[idx]);
int a = pq.top(), b = min(mini, a);
long long take = solve(nums1, nums2, sum + nums1[idx], b, idx + 1, count + 1, k, n);
pq.pop();
long long not_take = solve(nums1, nums2, sum, mini, idx + 1, count, k, n);
return max(take, not_take);
}
long long maxScore(vector& nums1, vector& nums2, int k){
return solve(nums1, nums2, 0, INT_MAX, 0, 0, k, nums1.size());
}
@codestorywithMIK bhaiya, I coded in C++ and did not use any separate function for popping from priority queue. This code also passed just 12 cases and then got TLE.
Indeed it gives TLE even after memoizing like this below :
class Solution {
public:
int K;
int n;
unordered_map mp;
long long solve(vector& nums1, vector& nums2, int sum, int min_el, int i, int count) {
if(count == K) {
return sum * min_el;
}
if(i >= n) {
return 0;
}
string key = to_string(sum) + "_" + to_string(min_el) + "_" + to_string(i) + "_" + to_string(count);
if(mp.find(key) != mp.end())
return mp[key];
int min_now = min(min_el, nums2[i]);
long take_i = solve(nums1 , nums2 , sum + nums1[i] , min_now, i+1 , count+1);
long not_take_i = solve(nums1 , nums2 , sum, min_el, i+1 , count);
return mp[key] = max(take_i, not_take_i);
}
long long maxScore(vector& nums1, vector& nums2, int k) {
K = k;
n = nums1.size();
mp.clear();
return solve(nums1 , nums2 , 0 , INT_MAX , 0 , 0);
}
};