Minimum Numbers of Operations to Make Array Empty - Leetcode 2870 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/minimum...
0:00 - Read the problem
0:15 - Drawing Explanation
8:47 - Coding Explanation
leetcode 2870
#neetcode #leetcode #python

[@vedanthbaliga7686]

It's 6:30am in India when you upload daily. waking up and solving a leetcode problems has become a daily habit. Thanks for everything you do neetcode🙏

[@satyamjha68]

Exactly , like now if I don't solve a leetcode problem ,I feel like I am missing something today.

[@user-bf7yz3qd2i]

@@satyamjha68 exactly , Same what i'm suffering from!!

[@jamessullenriot]

And this is the reason why so many crud apps at small to mid sized companies are over engineered piles of nonsense 😂

[@user-bf7yz3qd2i]

@@jamessullenriot is that good or bad?

[@jamessullenriot]

@@user-bf7yz3qd2i Its bad. There is nothing wrong with leetcode per se, and solving challenges like this. In fact, it's very helpful in a lot of ways. The issue comes in when people use this as a way to evaluate and hire based on ones ability to solve problems like this, and then go into a role where the job is anything but solving issues like this. There are FAANG companies, FAANG Wannabe companies, but 99%+ of other companies don't function like this. They mostly just need devs to come in, maintain, maybe build out a new feature now and again, and don't over complicate things so that when they leave, the next person in has no idea what they were doing or why. The problem is, content like this or adding "FAANG interview" to a title, gets pushed to the top and then devs thing this is real world. Maybe in San Francisco, but who wants to live in San Francisco

[@singletmat5172]

Small observation on the dfs solution. In the DFS alg you have the line "if res == -1, return -1". When I tested removing that line, the DFS alg will never return -1, those lines are never reached and it still passes, so I believe you can remove that line. Please correct me if I am wrong. Thank you for the daily challenge videos, it helps a lot.

[@user-tm8xm9eb3z]

Nice solution! I've done it using sorting; I don't know why I haven't thought about hashmap. Good job!

[@dilmurodabdusamadov5572]

Man, hit 100! Amazing.

[@aniketpatel8655]

Using ceiling is an awesome idea! 😃

[@elyababakova2125]

Wow! I't amazing! I couldn't come up with such an easy solution

[@XEQUTE]

🙏🙏🙏🙏🙏🙏 I did a medium problem for the first time in freaking 4 years by watching your video! - I couldn't even code it up after loooking after solution. - I still had to run it a few times before it gave the right solution - A good friend of mine said I should be able to write the code in paper to be able to clear interviews ( without editing , ide etc) - but i am not at that level so I still consider that a win and hope to get to that level ( and yes he is a microsoft emplyee at redmond and has coded up the soluion in whitepaper without an idea in front of me so I beleive that is the standard)

[@amen652]

Bro is goated thanks for working on the daily's man

[@eternal.strength]

Hello! Thanks for idea! Its possible to solve this problem without Counter ?

[@jacksonprice6324]

I'm curious what your thought process is to find the second solution? When I see the word minimum in the problem description I'm immediately thinking some sort of backtracking/DP with memo solution. It seems like a lot of these problems have a clever "trick" (like dividing the count by three and rounding up). It seems simple in hindsight but coming up with that in real time can be tricky. Does that come from just seeing a lot of different problems and being able to map the problem to past experience?

[@JacobWerzinsky]

generally if the problem involves frequencies, start by using a hashmap to count everything in one pass to see if it makes things easier. From there, think of ways you can take a frequency and translate it into an answer directly before doing anything too complicated. Thinking through hashmap solutions is typically faster than dp, so I just start there and if there is no hashmap solution I can think of then move on to dp. In this case, I recognized that every frequency if you keep subtracting 3 will always reduce to 1, 2, 3, or 4 cases (other solutions recognized everything can be reduced to 0, 1, 2). Either way would lead you to the realization that you are dealing with mods and division, and then work out a solution from there.

[@miaowcat1]

Ah ceiling is a nice idea instead of keeping track of remainder is 1 or 2.

[@krateskim4169]

thank you so much

[@shivamraj-xv3wt]

c++ solution: class Solution { public: int minOperations(vector& nums) { map mpp; bool check=true; int ans=0; for(int i=0;i

[@satyendranagar7656]

I did the same

[@davi_singh]

In this problem as soon as I read `minimum` I also instantly thought that this is some sort of decision tree, my final solution was pretty close main difference was I am still pretty new to python so instead of using `Counter` I was building the hash map with a loop

[@NikhilRaj-wv6nf]

thank you,

[@adrindevose7262]

Thanks for the great content. Probably a silly question but I am going to ask it. Is it possible to get the basic of DSA down(absolutely no prior experience) in less than 10 days for a coding challenge that is for an entry level apprenticeship at JPMorgan? From my research on Reddit, they ask basic to intermediate DSA questions. Any insight is appreciated.

[@johnsoto7112]

Depends on the topic and you tbh

[@asagiai4965]

I kind of like your solution and using ceiling. My only problem is when you show you solution without explanation (luckily you explain it on your video) It would be confusing.

[@Donquixote-Rosinante]

Does neetcode post his videos on this channel (neetcodeio) on his website 'neetcode all' category?

[@walkastray007]

Wow. This is extremely satisfying. I love this solution!

[@DNKF]

if res == -1 in first solution is not required, since res is never reaching -1

[@adityamishra6389]

Could you try to do problem 880 please. “Decode String at Index”

[@silent7152]

Thank you for daily uploads and please don't stop

[@kirillzlobin7135]

Amazing

[@sriharsha580]

I really liked the first solution, that is something I can come up in interview. why line 13 is required in the first code?

[@siddharthbahl5036]

It seems it is not required.

[@ahmedwaleed3630]

The if condition at line 13 in the memoization solution is not necessary. Thanks!

[@saipriyakarnati2275]

Please upload solutions for leetcode contests too.

[@AkshayAnil0-1]

🙌

[@asagiai4965]

Edit: I'm wrong with solution. (in some edge cases) This is my answer before I see your solution. (This is just one solution). (I believe it is not that efficient but can be improved upon. Time complexity is O(n^2) + ) The idea is to make an array. Maybe let's call this array "operations". Which will contains objects that contains information of those numbers something like; [{storedNumber: 2, currentCount: 4}, {storedNumber: 3, currentCount: 3}, {storedNumber: 4, currentCount: 2}] /you how to make this TL;DR / Short explanation for this solution. I use the power of modulo operation, division operation, floor operation, subtraction operation. function Count_Minimum_Operations(operationsArr) { let return_val = 0 operationsArr.map(item => { if (item.currentCount % 3 === 0) { //When it is divisible by 3 return_val = return_val + (item.currentCount / 3) return } else if (item.currentCount % 3 === 2) { //When it is not divisible by 3, but you have 2 extra return_val = return_val + Math.floor(item.currentCount / 3) item.currentCount = item.currentCount - (3 * Math.floor(item.currentCount / 3)) } if (item.currentCount % 2 === 0) { //When it is divisible by 2 return_val = return_val + (item.currentCount / 2) } else { //When it is not divisible by any number except 1 return_val = -1 } }) return return_val } Note: Edge Cases Such as 1.) if you only have 1 copy it returns -1 2.) 2 copies returns 1 + current minimum count 3.) 3 copies returns 1 + current minimum count 4.) 5 copies returns 2. + current minimum count 5.) 7 copies returns -1. cause you have an extra operation that can't be counted and more edge cases Are accounted for this solution.

[@zephedits7088]

Hey Dude Great videos, wanted to know if you needed a video editor/thumbnail designer for the channel?

[@noobchess2516]

can someone give me code that he wrote earlier the dfs one. if possible can you convert it cpp if not just python would be good too'

[@noobchess2516]

int dfs(int n, vector& dp) { if (n == 0) { return INT_MAX; } if (n == 2 || n == 3 || n==1) { return dp[n] = 1; } if (dp[n] != -1) return dp[n]; int res = min(dfs(n - 2, dp), dfs(n - 3, dp)) + 1; return dp[n] = res; } class Solution { public: int minOperations(vector& nums) { unordered_map mp; int n = nums.size(); for (int i = 0; i < n; ++i) { mp[nums[i]]++; } int maxi = -1; for (auto i : mp) { if (maxi < i.second) maxi = i.second; } vector dp(maxi + 1, -1); int ans = 0; for (auto i : mp) { if (i.second == 1) return -1; int ans1 = dfs(i.second, dp); if (ans1 != INT_MAX) { ans += ans1; } } return ans; } }; i got it

[@sachinpaul2111]

Isn’t this just coin change asked in a fancy way? I just solved the coin changes of the individual frequencies and chose their summation as the answer (if it’s infinite; then return -1)

[@asagiai4965]

technically yes. nice someone get it. (aka what's the minimum number of coins you can give or something)

[@dingus2332]

Could think about the Greedy Approach , but could not code it up :(

[@prajjwaldubey5787]

couldn't understand the ceil concept here can anyone explain ???

[@DJSTEVE42]

From what I managed to infer from this is that the minimum number of operations needed for any given number is always the minimum operations needed to form the last multiple of 3 plus a 1. for example the min no of ops to obtain 6 is 2(6//3 == 2). Now every number after 6 up until the next multiple of 3 (i.e 9) is always going to have a min no of ops = 3. This goes for 7, 8 which all have the min no of ops as 3 which is (min no of ops of 6 (2)+ (1) = 3) . After reaching 9 it is 9//3 becomes 3. Now every number after 9 till the next multiple of 3 which is 12 will have the min no of ops as 3(min ops of 9) + 1 = 4. this 4 will be the min no of ops for numbers 9, 10, 11. You can refer to the code below : class Solution: def minOperations(self, nums: List[int]) -> int: counter = defaultdict(int) for n in nums: counter[n] += 1 minimumOperations = 0 for k, v in counter.items(): if v == 1: return -1 if v % 3 == 0: minimumOperations += v//3 elif v % 3 >= 1: minimumOperations += v//3 + 1 return minimumOperations Assuming the counter stuff makes sense. if the frequency of any val is equal to 1 then the problem cannot be solved so we can instantly return -1. else if the freq is a multiple of 3 then we can add to the min no of ops as v//3 as a whole cuz we cant do better that that. However if v % 3 gives a reminder it means we are reminder steps off by the previous multiple of 3. for example 7%3 == 1 because the last multiple is 6 and like i said now if the min no of ops for a multiple of 3 is just the number floor division 3 (6 // 3 = 2). Now as i mentioned if we want to find the min no of ops for elements that arent a multiple of 3 we just need to find the min no of ops for the previous multiple of 3 and add plus 1 to it. So now since we have the reminder as 1 for 7%3. To find the min no of ops for 7 we need min no of ops of 6 + 1 which is nothing but 7//3 + 1 (2 + 1 = 3) Go to 6:54 this is where i understood

[@ahmadselim4799]

Title says maximum and not minimum, susge

[@NeetCodeIO]

Fixed

[@alexkul7721]

sloppy

[@achan3073]

This is related to Frobenius coin problem. en.wikipedia.org/wiki/Coin_problem