Minimize Maximum of Array - Leetcode 2439 - Python

Solving Leetcode 2439 - Minimize Maximum of Array, today's daily leetcode problem on April 4th.

0:00 - Read the problem
0:30 - Drawing Explanation
7:55 - Coding Explanation

leetcode 2439

#neetcode #leetcode #python

[abhayphanse]

I have almost 400 questions on leetcode now and still got stuck at this, it is in my opinion a one off problem (it is what it is). Dont be discouraged if not able to solve this, keep grinding . We always have neetcode to help us out

[scresat]

with every new problem, I'm getting intuition if I will be able to solve it on my own or not.
For this one, I came straight to you without writing a single thing on paper.

[akashsardar]

I got upset when I could not come up with a Binary search approach as mentioned in the Hint section of the problem but after watching the first 3-4 mins of your video I was able to solve it. You are really great at breaking down complicated problem statements in their lucidest form 🙏🏻🙏🏻Thank u NeetcodeIO.

[effyzhang]

I don't even understand the question to begin with, thanks so much for the video!!!

[MP-nyep]

Thank you so much for the daily leetcode problems ! Helps a lot !!! Keep it up

[yoonkeunkoh]

You are amazing.
You explain this problem as if explaining to 7 years old student.
Great Video

[mirkelor]

After listening 2 min of your video, suddenly the solution occurred in my mind and I continued. It was precisely the same as yours. Thank you for clarifying as best as every time

[ShivangiSingh-wcgk]

Great solution I was thinking the heap way and driving myself crazy. This is so elegant

[akifahmed]

You have explained the solution so simply. Keep up the good work

[netanelkomm]

Thank you so much, I actually thought of this idea but couldn't verify it for some reason myself. I watched your video and realized it was the same idea, so I implemented it and it worked.
New sub!

[krateskim]

how did you even come with this type of intuition, its amazing

[harshitbisen]

why a similar logic in c++ fails a test case?

Code:
class Solution {
public:
int nums) {
int total = nums[0];
int res = nums[0];
int n = nums.size();

for(int i = 1;i < n;i++){
total += nums[i];
int t = ceil(total/(i+1));
res = max(res, t);
}
return res;
}
};

Test case:
nums =
[13, 13, 20, 0, 8, 9, 9]
Output
15
Expected
16

[ZORO__OP]

Binary search is more initutive for this to solve in my opinion.

[ycc]

In the step of reaching index 2, value 1, why do we want to calculate the prefix sum of all 3+7+1, instead of only caring about the immediate adjacent pair of [7, 1]? Thank you.

[ayushdhiman]

Only video that helped me understand the problem fully thank you !!❤❤

[foobar]

why is average working here? why isn't median being used? i thought of something along these lines then went ahead with median and got WA.

[adityamangla]

How are you dividing the total by the length of the array? We can't just equally distribute the values right?

[formatted]

I thought I should write as a clarification: That the solution to this problem is based on the "pigeon hole principle". It's a very easy to understand principle, but once someone reads about it (on wikipedia or something), problems like this tend to become even more intuitive. (And there are slightly more tricky variants which become even easier to pick up on)

Another example: If you have 20 boxes, and you randomly place 30 balls into the boxes. What's the chance at least one box has 2 or more balls in it?
How about if you only have 21 balls? And what about 20 balls?

Hint: Due to pigeon hole principle, the answer for the first 2 problems require no calculations at all. The 20 balls question is trickier, and requires "stars and bars, " but it might be easier just to think about how many different ways you can place 20 balls into 20 boxes (absurdly high). And then how many cases have no boxes with 2 or more balls in it, and just give a guess to the nearest percent.

[fane]

please also solve this using binary search, else this is also a fantastic way

[twonwon]

I one question about this in the explanation that they have provided what if we do this operation one more time and select i=3 then the array will become
[5, 5, 3, 4]
So wouldn't this 4 be the minimum value ?
I think I am missing something here