Smallest Sufficient Team | Recur + Memo | Bit Manipulation Made Easy | AMAZON | Leetcode-1125

[@meeseeks1489]

How is this channel not popular? This is so high quality stuff

[@codestorywithMIK]

Means a lot to me. Thank you so much 🙏🙏🙏

[@codestorywithMIK]

I might get less views because of long video But trust me, Bit Manipulation won’t haunt in this qn if you see the entire video Thank you ❤❤❤❤❤

[@procontent23]

Dang, that's surprising

[@souravjoshi2293]

Bro, you are the only guy whose long video I always wait. Because I have always learned a lot from your long videos. You literally go to each line and reason out why it is written. No one can teach like you. People will realise it later

[@wearevacationuncoverers]

MIK, you should know that I get over excited when you post long video because there is so much to learn. The best thing is that even a new guy who has not studied past topics can understand your explanation just because you discuss each and every line of code. "WHY" of every line is important for me

[@floatingpoint7629]

i personally love 30+ min video because its full of insights and pitfalls to avoid i hope you do not decrease the length. and the people who do not watch its their loss because the interviews are evolving. i gave an interview in which i showed the most optimal approach but interviewer instead asked me to write brute force only which was tricky because it involved recursive backtracking 😅 so the optimum solution was around 12 lines the recursive one was around 30 lines.

[@sachinmohanty4577]

@codestorywithMIK today i was unable to do POTD because I don't have a good hold and understanding of dp bitmasking but u made it so easy ..I will try this problem now with dry run ... And one more request pls if possible entertain us with some dp bitmasking problem and their intuition as well.. And pls don't stop making these long explanation video it is really helpful ❤❤ Thanks for the explanation ❤❤

[@xiaoshen194]

Small creators (as compared to striver and CwH) like u and rivaan deserve immense support. Thnk u😊😊

[@codestorywithMIK]

Thank you ❤❤. Means a lot ❤❤

[@souravjoshi2293]

true man

[@password47403]

Nearly solved it own my own, thanks to your easy to grasp explanations. DP with bit-manipulation is just a technique which sounds very daunting at first but ab intuition khud se build up hone laga hai for such problems! Thanks again!

[@codestorywithMIK]

Believe me I am the happiest person when I read “ab intuition khud se build up hone laga hai” Thank you so much for sharing this ❤️❤️❤️🙏🙏

[@codestorywithMIK]

Also guys, Yes, you can use a vector as well to store your past result as DP instead of unordered_map Find the C++ code below : class Solution { public: int m, n; int target_mask; vector result; vector t; void solve(vector &people , int idx , vector &temp, int mask ) { if(idx == people.size()) { if(mask == target_mask) { if(result.size() == 0 || result.size() >= temp.size()) { //vector copy = temp; result = temp; } } return; } if(t[idx][mask] != -1) { if(t[idx][mask] = result.size()) return; solve(people , idx + 1 , temp , mask ); // no if( (mask | people[idx]) != mask) { temp.push_back(idx); solve(people, idx + 1, temp , mask | people[idx]); temp.pop_back(); t[idx][mask] = (temp.size() != 0 ) ? temp.size() : -1; } } vector smallestSufficientTeam(vector& req_skills, vector& people) { n = req_skills.size(); m = people.size(); unordered_map skills; //skill -> unique number for (int i = 0; i < n; ++i) skills[req_skills[i]] = i; // represent each person by a single bitmasked number (k'th bit represents if a person has the k'th skill or not) vector people_skill; for (auto &v: people) { int skill_bit = 0; for (string &skill: v) skill_bit |= 1

[@kartikkk4583]

yaar mai vo if condition nhi samjha jab hum check krte hai dp, but return krne se pehle ek aur check krte hau line 21., matlab mai janna chahta hu ki agar humne ek aisa function bnaya hai jo void hai and real answrr hum kahi aur store krre hai to memoize kis base pr kia jana chhaiye please iska video me explain krdo ya chat ki krdo koi baat nhi. , maine bi normal code ek dam same aapke vala style me hi kia tha , lekin memoize nhi kr paya , to aake video dekha but pura clear nhi hora kis base pe kia jaaye memoize and vo double check on line 21.

[@himanshudiwan8018]

Only place to jump into when I couldn't able to make daily Leetcode question !! Keep going bro!!!

[@codestorywithMIK]

Thanks a lot Himanshu ❤️❤️

[@jagratgupta8392]

Kya explanation tha sir...!!!...itne tough question ko Aise samjha Diya jaise isse easy koi question na ho...great sir understood very clearly❤❤

[@codestorywithMIK]

Thank you so so much ❤️🙏

[@jagratgupta8392]

@@codestorywithMIK Sir You deserve much much better ....keep it up sir ...Thanks for the solutions daily😊

[@shabananoor9423]

It was the only code and explanation I could understand since morning. Thanks a lot

[@ManojKumar-pv4rx]

Bhayya Apka explanatio of bit manupaltion is too good....

[@codestorywithMIK]

Thanks a lot Manoj ❤️❤️

[@souravjoshi2293]

And AGAIN - HARD made EASYYYYYYYYY You are gifted, you can make Hard problem look like a cake walk

[@TanishMahi-k6h]

Thank you for explaining the skip/take methodology! Respect!!

[@codestorywithMIK]

Glad it was helpful!😇🙏

[@kishan.17]

We should all appreciate your efforts asking videos which are 30 min above which requires more skills and patience ,thank you sooo much for your efforts we love u sooo much .❤

[@souravjoshi2293]

Totally agree bhai. This guys is a living LEGEND

[@wearevacationuncoverers]

Indeed. This guy deserves respect

[@codestorywithMIK]

It means a lot guys 🙏🙏🙏

[@AnandKumar-kz3ls]

great explanation result = temp this also takes O(N) time so i think time complexity would be 2^m * n * n where m= no of skills and n = no of people

[@kishan.17]

Your voice is super ur Explanation is super Ur consistentey is super ,your story telling is super .... Love u sooo much super 👌 bro❤❤❤

[@codestorywithMIK]

Hi Kishan, Your kind words and generosity made my day. Thank you for making my Sunday even better ❤️❤️❤️

[@kishan.17]

​@@codestorywithMIKthanks bro ur videos are my motivation in solving daily challenges I learn from ur videos everyday and ,from past 1 month ur videos though me more then any other dsa course, ❤.

[@codestorywithMIK]

@kishan.17 I am so happy to hear this ❤️🙏

[@Engineer_With_A_Life]

This was the exact explanation I was looking for. Appreciate your efforts!

[@codestorywithMIK]

Thanks a lot Ayush ❤️❤️😇

[@anuppatankar4294]

Mastering Complex Problems with Ease 👌🏻

[@sak4531]

kya baat h mere bhai... faad explanation h!!! Extra points for quality of video and Voice... Subscribed!!

[@codestorywithMIK]

Welcome to my small channel 😇❤️ Thank you so much 🙏🙏❤️

[@GeniusOG]

You are Great.Thanks For the great video.😊

[@codestorywithMIK]

Thanks a lot 😇❤️❤️

[@RahulSharma-ht2xz]

this channel deserves so much more. =) you will get one day with your hard work.

[@codestorywithMIK]

Thank you so much ❤️🙏

[@Piyushraj0]

Awesome explanation as always bhaiya ❤

[@codestorywithMIK]

Thank you so much Piyush ❤️🙏

[@dhairyachauhan6622]

bro never stop making such videos. You teach very well and if you get time you can upload contest upsolving vids, it will increase your reach since all the people who do that teach really bad :)

[@codestorywithMIK]

Thank you so much ❤️🙏😇 Soon trying to squeeze my travel time to make contest ones too

[@yashpadiyar4952]

@@codestorywithMIK Ya please❤❤

[@samreenjahan2482]

@@codestorywithMIK Yes sir, solving the contest problem is very challenging sometimes, please upload videos on the contest also.

[@wearevacationuncoverers]

wow. it no more seems hard at all 😅 I didn't know bit logic is this easy. I was scared of bit

[@decostarkumar2562]

I ❤ the roughness of your code ....

[@mohithadiyal6083]

As always Best explanation 👍😊

[@MounikaEMB]

Video is long but great explanation Thank you for your patience 😊

[@codestorywithMIK]

Most welcome 😊❤

[@puneetkalra9688]

Best Explanation

[@floatingpoint7629]

thanks for the explanation. it was very helpful

[@vathsalanagaraju]

your have excellent teaching skills, convert these video to english , i am 100% sure that it will more popular than others.

[@sauravbiswajit8091]

Absolutely Great explanation 😃

[@codestorywithMIK]

Thank you so much 🙏❤️😇 Also, do have a look at my comment, i have also added memoization using vector instead of map.

[@wearevacationuncoverers]

Was waiting for your video only

[@atharvasingh5568]

Great buddy....

[@codestorywithMIK]

Thank you so much 🙏❤️😊

[@rohanchoudhary5523]

Amazing effort

[@codestorywithMIK]

Thank you so much Rohan for your kind words ❤️❤️

[@39_jatinjain4]

nice explanation 🙂🙂

[@codestorywithMIK]

Thank you Jatin 😇

[@Bibhukalyan_iitkgp_21]

Sir please aap video se pehle jo 10-20 seconds ka Bhasan (Motivation) dete the wo continue kariye har video me ...... Usse dekh kar hi lion ka energy aajata hai Thanks so much sir

[@codestorywithMIK]

I always give that in my concepts playlist. But sure I will now add it in my other videos too. Thank you for your feedback. Also, you can see my motivation videos here too - instagram.com/codestorywithmik?igshid=OGQ5ZDc2ODk2ZA==

[@Bibhukalyan_iitkgp_21]

@codestorywithMIK sorry sir I don't have instagram account But sir one thing to inform u abhi sham me mera Adobe ka Test tha aapke explanation ke upar ek Dp ka qs aaya tha aram se ho gya

[@codestorywithMIK]

@Bibhukalyan_iitkgp_21 Wowwwww. I am so happy to hear that ❤️❤️❤️🙏🙏🙏

[@Bibhukalyan_iitkgp_21]

@@codestorywithMIK Sir can you please make a video on Egg Drop Question ,I think no one has given proper explanation on YT thanks

[@spandanrastogi7144]

3 Doubts : D1. Why dp needs to updated inside if condition and not outside ? D2. Why dp is updated with -1 when temp.size() is 0 ? D3. Also, keeping a dp tells us that weather the result for this state has been calculated earlier or not. So, Why can't we just keep a dp vector and check if it contains the key or not? If contains, It will mean that the result for this state has been calculated earlier so we can just return otherwise we will keep exploring this path further.

[@codestorywithMIK]

1. You can update dp outside of if as well. It won't effect the result. It would just be unnecessary. So you can keep it outside and it works fine as I checked. if( (mask | people[idx]) != mask) { temp.push_back(idx); solve(people, idx + 1, temp , mask | people[idx]); temp.pop_back(); } dp[s] = (temp.size() != 0 ) ? temp.size() : -1;

[@codestorywithMIK]

2. DP is updated with -1 just to let us know that for this particular state (idx and mask), the soution has not yet been calculated in the past. Since I am storing size of temp in DP, so storing -1 makes sense as size of temp can never be -1 and clearly tells me that it was not calculated in past.

[@codestorywithMIK]

3. Yes, you can definitely use a vector as well to store your past result. Find the code below : class Solution { public: int m, n; int target_mask; vector result; vector t; void solve(vector &people , int idx , vector &temp, int mask ) { if(idx == people.size()) { if(mask == target_mask) { if(result.size() == 0 || result.size() >= temp.size()) { //vector copy = temp; result = temp; } } return; } if(t[idx][mask] != -1) { if(t[idx][mask] = result.size()) return; solve(people , idx + 1 , temp , mask ); // no if( (mask | people[idx]) != mask) { temp.push_back(idx); solve(people, idx + 1, temp , mask | people[idx]); temp.pop_back(); t[idx][mask] = (temp.size() != 0 ) ? temp.size() : -1; } } vector smallestSufficientTeam(vector& req_skills, vector& people) { n = req_skills.size(); m = people.size(); unordered_map skills; //skill -> unique number for (int i = 0; i < n; ++i) skills[req_skills[i]] = i; // represent each person by a single bitmasked number (k'th bit represents if a person has the k'th skill or not) vector people_skill; for (auto &v: people) { int skill_bit = 0; for (string &skill: v) skill_bit |= 1

[@spandanrastogi7144]

@@codestorywithMIK I meant dp as a of vector of string, But Thank you so much for replying and putting in so much efforts. Watching your solutions everyday since start of the year.

[@Rajat_maurya]

Learned something new, how to use bit manipulation in these type que

[@codestorywithMIK]

Thank you for watching Rajat ❤️❤️

[@rohitshah8904]

Was unable to solve today's question now I think I can

[@codestorywithMIK]

Let’s do it 💪💪 That’s the spirit Rohit ❤️❤️

[@rohitshah8904]

​@@codestorywithMIKthanks ❤

[@satvrii]

❤❤❤ thanks alot, gbu

[@princepawar5655]

Bhai is dp ko sbb se alag bnana .. Vaise to alag h ni .. Mtlb all types of pattern cover karna Bhot acha kaam kar rhe ho...

[@codestorywithMIK]

Sure thing. Thank you so much 😇❤️

[@prajwalshaw9217]

Sir plz bring a video on leetcode 376 ..wiggle subsequence. It's bottom up approach is very confusing. Thanks:)

[@kamranwarsi12b22]

One question like on online coding rounds and face to face interviews do we have to write full code or a function will be given and we have to complete it like on coding platforms ??

[@codestorywithMIK]

If it’s an OA (online assessment), you will have to submit and get all the test cases Accepted. Now coming to face to face, it’s not fixed, sometimes they only ask Pseudo code, sometimes entire code, sometimes only pseudo code with a complete dry run

[@kamranwarsi12b22]

@@codestorywithMIK ohkk thnxx

[@thanujjanugani899]

very good explanation. you are awesome bro. I have one doubt: how are we soo sure that if temp.size()>0 , we update dp[key] = temp.size() in the solve function at last. during the process, we will go through all combinations and return from the base case right. so, there is also a chance that we update dp value even if we dont find an answer. can you please clarify?

[@easyvedicmaths886]

sir, how you got to know that this is Dp question without looking at constaints? and how one will get to know that Bit manipulation is required in the question?

[@yashgarg3027]

bhaiya 1 doubt in starting jo hum bit zero le rahr h vo zero unlimited zeros ka hota hain exam int skillbit = 0 then skillbit will be of in starting 00000000....00 plz clear bhaiya if i am wrong

[@codestorywithMIK]

That is a decimal 0 And it’s bit representation will be 000000000…. upto 32 bits in 32 bit machine or 64 bit in 64 bit machine

[@codeandtalk6]

❤

[@codestorywithMIK]

Thank you for always watching my videos. 🙏❤️

[@codeandtalk6]

@@codestorywithMIK thank you bro you always make this hard problems very easy.

[@hello-world8906]

Recursion wala code mein kya galti hai? not passing tc: ["mmcmnwacnhhdd","vza","mrxyc"] [["mmcmnwacnhhdd"],[],[],["vza","mrxyc"]] class Solution { public: int m, n; int target_mask; vectorans; void solve(int i, vector&people_skills, vector&temp, int mask){ if(i == n){ if(mask == target_mask){ if(ans.size() == 0 || ans.size() >= temp.size()){ ans = temp; } } return; } if(ans.size() != 0 && temp.size() >= ans.size()) return; //skip solve(i+1, people_skills, temp, mask); //take if((mask | people_skills[i]) != mask){ temp.push_back(i); solve(i+1, people_skills, temp, mask | people_skills[i]); temp.pop_back(); } } vector smallestSufficientTeam(vector& req_skills, vector& people) { m = req_skills.size(); n = people.size(); unordered_mapskills; vectorpeople_skills; for(int i = 0; i < m; i++){ skills[req_skills[i]] = i; } for(auto &v : people){ int skill_bit = 0; for(string &s: v){ skill_bit |= 1

[@kartikkk4583]

maine same solution kia, but memoization me atak gya

[@empvaibhav9799]

W

[@aakshatmalhotra8088]

memoizing void functions are a bit confusing

[@codestorywithMIK]

Indeed. Actually the reason i did this was because in this qn we had to return an array of indices and hence I didn’t want to return an array from function. That’s why, keeping a global result and updating it everytime helped to simplify

[@Aditest-kc2jy]

Agree, @codestorywithMIK, I still did not understand why this memoization code worked dp[s] = (temp.size() != 0 ) ? temp.size() : -1;

[@codestorywithMIK]

@Aditest-kc2jy For every recursive call for a particular idx and mask, temp will have certain values. We are only storing the size of temp for every particular recursive call having idx and mask as the parameters. Now, whenever we see this mask again in future, we will know that temp was calculated in the past for this idx and mask. Now if this dp[s] has a better temp.size() than current then there is no need to move further and hire any employee and that’s when we return. I hope it helps ❤️❤️

[@Aditest-kc2jy]

@@codestorywithMIK understood, thanks, it is clear now. hey MIK, I would really appreciate if you can quickly discuss time and space complexity in your videos.

[@codestorywithMIK]

@Aditest-kc2jy Yes yes, actually I missed to discuss TC in this one. i will definitely keep that in my mind Thanks a lot 😇🙏❤️

[@bytecoding9685]

I guess what we are doing is just improving the backtracking conditions we added a map just to check if the problem was solved earlier with x set of people if we already solved the problem with x(2) set of people size which is less than y(3) then we dont need to solve for y people size so we backtrack. Below is the java implementation. class Solution { List result; HashMap dp; public int[] smallestSufficientTeam(String[] req_skills, List people) { //use bit manipulation to save space int n=req_skills.length; int value=(int)Math.pow(2,n)-1; int peopleSkills[]=new int[people.size()]; Map positionOfRequiredSkills= new HashMap(); for(int i=0;i

[@aaravmishra3487]

is the time complexity O(2^(n+m)), n*m as because we might have m different masks for people with n skills? Java implementation: class Solution { // BitMask DP private int n, m, targetMask; private List result; private Map dp; public int[] smallestSufficientTeam(String[] req_skills, List people) { this.n = req_skills.length; this.m = people.size(); this.result = new ArrayList(); this.dp = new HashMap(); Map mp = new HashMap(); // skills -> unqiue idx number for(int i = 0; i < n; i++) { // calculating unique id's for each skills String skillName = req_skills[i]; mp.put(skillName, i); } List peopleSkill = new ArrayList(); for(List skills: people) { // convert each skills into relevant decimal respresentation using bit maipulation int skillBit = 0; for(String skill : skills) { skillBit = skillBit | (1 = tmp.size()) { result = new ArrayList(tmp); } } return; } String key = Integer.toString(idx) + "_" + Integer.toString(mask); if(dp.containsKey(key)) { if(dp.get(key) = result.size()) return; // pruning as we don't need result with larger size than curr result solve(peopleSkill, idx+1, tmp, mask); // notTake if((peopleSkill.get(idx) | mask) != mask) { // to verify whether this person do have a skillset or not tmp.add(idx); // take solve(peopleSkill, idx+1, tmp, (mask | peopleSkill.get(idx))); tmp.remove(tmp.size()-1); dp.put(key, tmp.size() != 0 ? tmp.size() : -1); } } }