Profitable Schemes - (AMAZON) | Recur+Memo | Leetcode-879 | Live Code + Explanation

This is the 25th Video on our Dynamic Programming (DP) Playlist.
In this video we will try to solve a very good DP Problem "Profitable Schemes" (Leetcode - 879)
Trust me, this will no longer be a Hard Problem. I will explain the intuition so easily that you will never forget.
We will solve it using Recursion + Memoization technique
Later we will post another video in which we will solve it using Bottom UP DP
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Profitable Schemes
Company Tags : AMAZON
My solutions on Github : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[@NamanSharma-zx6gq]

Sir, I have been watching your videos regulary and because of that I was able to solve today's question all by myself. Thank you , because of your videos I am able to improve my problem solving

[@codestorywithMIK]

Apologies for the delay guys. Little busy this week due to festival. Hope you guys will understand ❤️❤️❤️

[@kamleshsinghbisht130]

Eid Mubarak Bhai Jaan💓

[@codestorywithMIK]

Eid Mubarak Kamlesh. Thank you so much ❤️❤️❤️

[@turing_machine544]

Eid Mubarak Bhaiya

[@kamleshsinghbisht130]

@@codestorywithMIK Keep Up The Good Work!

[@sanjaykatta6499]

I have almost solved a hard problem. Just got stuck at memoizing the third component profit, otherwise I almost did it. Thank you for all your explanations and intuition building. It would've never been possible otherwise.

[@niteshk0487]

question dekhne ke bd or read krne ke bd itna hard lga sb sir ke upr se gya after watching your explanation easy or wot🤣❤❤

[@codestorywithMIK]

Time Complexity :- O(N*M*K) N is the maximum number of criminals allowed in a scheme, M is the size of the list group, and K is the value of minProfit. Space Complexity :- O(N*M*K)

[@ManojKrVerma-vw4dx]

if v r nt memoising its time complexity is 2^N . Am I correct ?

[@codestorywithMIK]

Yes because at each position you have two choices. So TC is exponential

[@anuppatankar4294]

Watched your explanation and solved it myself. Great Video ❤

[@codestorywithMIK]

Awesome Anup ❤️❤️❤️

[@codewalalove8783]

Sir, apki vedio ka morning se wait kr rahe hai, i saw 3-4 vedio more before that of same question, but smj nhi aya. I really like your way of explaning the things.Thnak You :)

[@codestorywithMIK]

Awesome. So glad. Thank you so much ❤️❤️❤️

[@souravjoshi2293]

I see many videos, but the satisfaction comes from your videos. Thanks a lot Eid Mubarak

[@codestorywithMIK]

Thanks a lot Eid Mubarak ❤️❤️

[@k_CO_Sachin]

Amazing the idea to take minimum.... I was stuck at this step

[@shikharpandya4927]

Thank u sir did it on my own

[@vineetkumar2899]

Thank you so much for this awesome explanation of hard problem. Eid Mubarak Bhaiya.💥💫

[@codestorywithMIK]

Thanks a lot Vineet ❤️❤️❤️

[@romanraihan9133]

long long not_taken = solve(i+1, p, people, minProfit, group, profit)%mod; long long taken = solve(i+1, min(p+profit[i], minProfit), people+group[i], minProfit, group, profit)%mod; we are doing mod here. so we don't need to do (taken%mod + not_taken%mod)%mod; only (taken + not_taken) %mod; should work. just a simple improvement. Thanks for the tutorial. I was waiting since 6am for this video.

[@codestorywithMIK]

Yep yep absolutely correct. Thanks a lot ❤️

[@iamnoob7593]

Again fantastic Explanation

[@prajwalshaw9217]

Thanks for a wonderful explanation sir. But facing a bit problem while coming up with it's bottom up approach...eagerly waiting for the bottom up approach of this question.

[@saurabhkumarsingh9550]

Nicely explained.... I am new to your channel... I must say your explanation is good.

[@codestorywithMIK]

Thank you so much Sourabh and welcome to my channel ❤️❤️

[@arjunsolanki2612]

Once again thank you bhaiya. Eid mubarak❤

[@codestorywithMIK]

Thanks a lot Eid Mubarak ❤️❤️

[@abc-ym4zs]

I am your new subscriber I saw your channel in the linkedin saying u are approach to a problem is really good like on which topic your uploading questions dialy how to get maximum of your playlist how to follow your playlist sir

[@codestorywithMIK]

Thanks a lot. Welcome to my channel. Right now I post Leetcode Daily Challenge And if you checkout my channel, it has playlists for different topics. If you want to make Graph easy, you can start my “Graph Concepts & Qns” playlist.

[@abc-ym4zs]

@@codestorywithMIK ok sir

[@humanity7880]

That minProfit wala explanation was too good,but can you explain me one thing: before that i was trying to do by making a dp[101][101][10001] by assuming that maxProfit will be of 10000 because in question was given profit[i]'s max value is 100 and profit's max length is 100 so i take 100*100=10000 and +1 that makes it dp[101][101][10001] but that was not working. Am i right profit dows not exceed 10000?

[@Imrockonn]

🎉

[@codeandtalk6]

❤

[@naeemkhan4534]

Bro What do you use to record the videos? Which tablet and software

[@codestorywithMIK]

Ipad 11 pro I use default Notes app in it and use default screen recording

[@shaamidrees6036]

Thanks you brother

[@codestorywithMIK]

Thanks a lot Eid Mubarak ❤️❤️

[@Tech_Creater_]

Could you explain this question in dp tabular method ?

[@codestorywithMIK]

Sure. Will upload soon. Just a little occupied now due to festival

[@manimanohar_001]

Bhaijaan Eid Mubarak🌛.

[@codestorywithMIK]

Eid Mubarak ❤️❤️❤️

[@YashSinghal]

new mic ?🤔 Eid mubarak 🎉🌙

[@codestorywithMIK]

No new mic yet. But soon ❤️ Eid Mubarak ❤️❤️

[@ManojKrVerma-vw4dx]

why are u checking whether we found one way after reaching end of the array. Is it not correct to say as soon as we get one way we should increase the count by 1?

[@codestorywithMIK]

Because we want to explore different paths. And if we return as soon as we get minProfit, then we might miss other profitable paths from that point further

[@ManojKrVerma-vw4dx]

@@codestorywithMIK as soon as we get minProfit we increase the count by 1 and continue exploration further I never say return. I was doing the same and getting the answer always more than the actual answer. Why ?

[@codestorywithMIK]

Can you share your code

[@codestorywithMIK]

You need to ensure that you dont exceed the number of members greater than n

[@ManojKrVerma-vw4dx]

@@codestorywithMIK Here is my recursive code void helper(int idx, vector& group, vector& profit, int pprofit, int minProfit, int persons, int maxPersons, int sz, int &cnt){ if (idx >= sz) return ; if (pprofit >= minProfit and persons < maxPersons) cnt++; // option 1 leave this group helper(idx+1, group, profit, pprofit, minProfit, persons, maxPersons, sz, cnt); // select this group if possible if (persons+group[idx] = minProfit and persons < maxPersons) cnt++; return ; }

[@informative180]

u r too gud..❤

[@codestorywithMIK]

Thank you so so much

[@shivangiagrawal3971]

pls share today's daily leetcode question sooner

[@codestorywithMIK]

Hello Shivangi, Actually I couldn’t get time to post today’s leetcode due to festival. But feel free to find the code in my Github repo. And i will post tomorrow.

[@shivangiagrawal3971]

@@codestorywithMIK ok Eid Mubarak ji apko

[@codestorywithMIK]

Thank you for understanding Shivangi. Eid Mubarak 😊

[@atifhu]

EID MUBARAK🌙

[@codestorywithMIK]

Eid Mubarak ❤️❤️

[@anubhavsingla3126]

class Solution { int MOD = 1000000007; public int solve(int n, int p, int i, int[] group, int minProfit, int[] profit, int[][][] dp) { if(i == group.length) { return p >= minProfit ? 1 : 0; } if(dp[i][n][p] != -1) return dp[i][n][p]; int ans = 0; ans = solve(n, p, i+1, group, minProfit, profit, dp); if(n - group[i] >= 0) ans += solve(n - group[i], Math.min(p+profit[i], minProfit), i+1, group, minProfit, profit, dp); return dp[i][n][p] = ans % MOD; } public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) { int[][][] dp = new int[group.length+1][n+1][minProfit+1]; for(int[][] row: dp) { for(int[] col: row) { Arrays.fill(col, -1); } } return solve(n, 0, 0, group, minProfit, profit, dp); } } java version of recur + memo

[@AnkitSingh-tm5dp]

I solve almost 90% but memo give some pain after understand the logic of min(profit+curr,miniproft) 🥲 i feel coding is really interesting thanku sir

[@codestorywithMIK]

So glad Ankit. 90% is all that I want. Soon very soon, we all will reach 100% together 💪💪💪 Thank you so much ❤️❤️❤️

[@voice6905]

But I didn't understand why min(profit, profit[i] + currentProfit) works?