Minimize Maximum of Array - Leetcode 2439 - Python
VloĆŸit
- Äas pĆidĂĄn 23. 07. 2024
- đ neetcode.io/ - A better way to prepare for Coding Interviews
Solving Leetcode 2439 - Minimize Maximum of Array, today's daily leetcode problem on April 4th.
đ„· 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/minimiz...
0:00 - Read the problem
0:30 - Drawing Explanation
7:55 - Coding Explanation
leetcode 2439
#neetcode #leetcode #python
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
Same I have also solved around 300 and was stuck how to approach andin mind i was stuck with max heap approach
Brilliant solution and explanation!
im on 600 and still shit bro lol
> 500 here, and still cannot solve it
550 and also got stuck at this problem
he came when we needed the most
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.
Thank you so much for the daily leetcode problems ! Helps a lot !!! Keep it up
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.
You have explained the solution so simply. Keep up the good work
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!
You are amazing.
You explain this problem as if explaining to 7 years old student.
Great Video
Great solution I was thinking the heap way and driving myself crazy. This is so elegant
Only video that helped me understand the problem fully thank you !!â€â€
I don't even understand the question to begin with, thanks so much for the video!!!
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
Right on time! Thank you!
how did you even come with this type of intuition, its amazing
Very nice! Thanks !
thank you so much for the vedio it helps me a lot........
good work , thank you
How are you dividing the total by the length of the array? We can't just equally distribute the values right?
Really good video
thanks
please also solve this using binary search ,else this is also a fantastic way
you are genious
I had compilation error @line 7 because there is to +i add in total ( total + i ) / ( i + 1 )) not sure how it running right there. Please check
why are you adding i to total? it should be total/(i+1)
why a similar logic in c++ fails a test case?
Code:
class Solution {
public:
int minimizeArrayValue(vector& 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
My guess is that your ceil() method call is not working, since in C++, dividing integers results in an integer rather than a float. You prob want to cast total as a float or double before dividing
use
int t = ceil (double(total)/double(i+1));
bcz you used int/int which will always give u int only no advantage of ceil
also used long long for total else overflow may occur
Correct way is (int) ceil((double) total/(i+1))
Casting value inside the ceil to double, then casting the return of ceil to int since ceil returns a double value.
class Solution:
def minimizeArrayValue(self, nums: List[int]) -> int:
sum_val = nums[0]
count = 1
max_val = nums[0]
for r in range(1,len(nums)):
sum_val+=nums[r]
count+=1
avg_val = math.ceil(sum_val/count)
max_val = max(max_val,avg_val)
return max_val
dayummmm love u
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.
Tricky one, yeah
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
Stumbled upon the same, but: No, because we always get the overall array max, so overall max in the array is still 5 (see [5,5,3,4] ) even if we modify some other part to have a smaller max, it will make no difference.
@@sandagolcea4966 yes when you put it this way it makes sense. Thanks for replying !
I came up with a solution in 35 minutes
Don't understand what you mean by "we can't move values to the left" / right. đ€
moving a value to left means decreasing the current value and increasing the left value. Imagine it like a number flew towards the left hence reduced the current value by 1 and increased the left value by 1.
man i tried heap sol, but couldnt get it to pass. Not sure where the error is:
class Node:
def __init__(self,val,left=None,right=None):
self.val=val
self.left=left
self.right=right
def __lt__(self, other):
return self.val int:
heap=[]
curr=h=Node(float('inf'))
for j in range(len(nums)):
node=Node(-nums[j])
curr.right,node.left=node,curr
heappush(heap,node)
curr=curr.right
out=heap[0].val
while True:
if heap[0].left==h or heap[0].val+1==0: #cant make smaller
return -heap[0].val
node=heappop(heap)
node.val+=1
node.left.val-=1
heappush(heap,node)
if heap[0].val>=out:
out=heap[0].val
else:
break
return -out
Testcase: [13,13,20,0,8,9,9]
output: 15
Expected: 16