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

0:00 - Read the problem
0:15 - Drawing Explanation
8:47 - Coding Explanation

leetcode 2870

#neetcode #leetcode #python

[vedanthbaliga]

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🙏

[singletmat]

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.

[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)

[ИгорьКабаков-зм]

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

[amen]

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

[shivamraj-xvwt]

c++ solution: class Solution {
public:
int minOperations(vector<int>& nums) {
map<int, int> mpp;
bool check=true;
int ans=0;
for(int i=0;i<nums.size();i++)
{
mpp[nums[i]]++;
}
for(auto it:mpp)
{
if(it.second==1)

{
check=false;
}
else if(it.second%3==0)
{
ans+=it.second/3;
}
else if(it.second%3==1)
{
ans+=((it.second-4)/3)+2;
}
else if(it.second%3==2)
{
ans+=(it.second/3)+1;
}
}
if(check)
{
return ans;
}
else return -1;
}
};

[elyababakova]

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

[silent]

Thank you for daily uploads and please don't stop

[jacksonprice]

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?

[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

[asagiai]

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.

[walkastray]

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

[eternal.strength]

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

[adrindevose]

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.

[DNKF]

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

[ahmedwaleed]

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

[saipriyakarnati]

Please upload solutions for leetcode contests too.

[sriharsha]

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

[asagiai]

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 {
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.

[adityamishra]

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