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
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.
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.
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
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
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.
It fails in python too now. You can use below method to calculate ceil instead of math.ceil Instead of math.ceil(total/(i+1)) use total + (i+1) -1 // (i+1) Simplified version total + i // (i+1)
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!
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.
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.
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
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
Same here, at 400+, still stuck and came for solution.
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.
how is this a binary search approach?
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.
I don't even understand the question to begin with, thanks so much for the video!!!
Thank you so much for the daily leetcode problems ! Helps a lot !!! Keep it up
Great solution I was thinking the heap way and driving myself crazy. This is so elegant
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
You have explained the solution so simply. Keep up the good work
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.
It fails in python too now. You can use below method to calculate ceil instead of math.ceil
Instead of math.ceil(total/(i+1))
use total + (i+1) -1 // (i+1)
Simplified version
total + i // (i+1)
You are amazing.
You explain this problem as if explaining to 7 years old student.
Great Video
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!
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.
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
how did you even come with this type of intuition, its amazing
How are you dividing the total by the length of the array? We can't just equally distribute the values right?
that is what im thinking too, i am having trouble understanding why this works.
Only video that helped me understand the problem fully thank you !!❤❤
Right on time! Thank you!
please also solve this using binary search ,else this is also a fantastic way
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.
thank you so much for the vedio it helps me a lot........
Don't understand what you mean by "we can't move values to the left" / right. 🤔
Very nice! Thanks !
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 !
good work , thank you
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)
thanks
Really good video
I came up with a solution in 35 minutes
you are genious
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
Tricky one, yeah
dayummmm love u