Minimize the Maximum Difference of Pairs - Leetcode 2616 - Python
Vložit
- čas přidán 9. 07. 2024
- Solving Leetcode 2616, Minimize the maximum difference of pairs, today's daily leetcode problem on august 8.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 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
1:10 - Drawing Explanation
11:40 - Coding Explanation
leetcode 2616
#neetcode #leetcode #python
Tried talking a bit slower in this one, let me know if it's better/worse.
Also, I would be uploading daily but most of the daily LC problems lately have been ones I already have videos for :)
not all heroes wear capes
Great video! Could you please also share the DP solution for this one?
You can upload your other videos that you say on podcast that I have a bunch of recorded videos to upload!!
Yes, please continue with the daily leetcode problems. It's so helpful
Thanks for the explanation. The right boundary should be nums[-1]-nums[0] after sorted nums instead of 10**9. This will reduce the running cycles.
*log is square root on steroids* - I can never forget this now
lol "log is square root on steroids" brilliant solution with clear explanation as always, plz keep these daily challenges coming
Thanks for the daily
Similar problems: (pattern is to binary search and test)
875. Koko Eating Bananas
1011. Capacity To Ship Packages Within D Days
1870. Minimum Speed to Arrive on Time
A slight optimization can be binary searching the range from 0 to (max(arr) - min(arr)) as the max diff of any pair is bounded by this upper limit.
Nice catch!
And since you've sorted the array, might as well just take the difference of (last element - first element).
@@DanielRodrigues-bx6lrexactly
@@DanielRodrigues-bx6lr yeah! I did the same thing, and this tweak made my code faster than 90%
It is really good, but we can choose the range as 0 to (arr[length - 1] - arr[0]) coz the maximum result we get is the diff between last and first elements.
It's great to see you back!
One more very small performance improvement is that we can avoid calling "abs" every time we find the difference. Instead we can just find the difference like nums[i+1]-nums[i] as the array is sorted now.
(a + b) / 2 = a/2 + b/2 = a - a/2 + b/2 = a + (b-a)/2
Just writing it as: `a/2 + b/2` would be both sufficient and easier (to graps) to prevent overflow.
if we do l+r then their sum could overflow(be greater) than the max allowed capacity, so instead we take their difference and add it to the left pointer
Whenever we see in Question to Find Min(Max) or Max(Min) we will try to use Binary search and here in this question s = 0 and e = max element in my array;
Great video man
Hi there, please provide the dynamic programming solution also. (code reference or similar question solution will also work). Thanks!
lots of support from india
can we have a feature to take only required courses from the website instead everything
Great video
Constraints: 0
I have been following your 150 problems as well as leetcode's for the last 1.5 months. I have done around 80 (35 easy, 40 medium, 5 hard). But even still when I encounter a new problem in the medium or hard section from the topics I have covered till now(nothing from tree or dp or backtracking yet), I almost always have to lookup a solution. or I just wouldn't be able to solve it. I dunno if I am improving or not if I have to always look up a solution. I do revise the problems the next day. And try to solve them on my own if I had to take help on the first try. Is there any advice you could give?
write down your approach in google sheets or on paper to recall what you are thinking when you are trying to solve that problem earlier;
how can i be like you man, you are like genius or smth
please someone give us the dynamic programming solution in python please
Can you explain that mid pointer why l + (r-l)/2 is preventing overflow
Imagine you have a data type that overflows at 16 (valid range 0 to 15)
Find the average of 10 and 8.
(10 + 8) / 2 overflows when 10 is added to 8, because 18 is greater than 15.
8 + (10 - 8) / 2 does not overflow, because you never risk adding two very large numbers.
However, in Python I don't think integers can overflow. This is certainly a concern in languages like C++.
The alternative is using r+l /2. The r+l piece can over flow
idk why.... I am never able to solve problems like these by myself 😞
It needs lots of understanding and practice
this should be a hard level question
The way he says log is sqare root on steroids🤣
there is a test case in it where p=3 and the o/p is 1, how is it possible like the set of minimums at best can be [2,1,0] 2 is the correct answer how did you cleared that, its testcase some 400ish
Why is it suddenly OK to naively check only neighbours when the array is sorted? In your example you checked only the tuples (1, 1), (2,3), (7, 10). but you could for example start from (1, 2), (7, 3) ...
I don't get it
same question here
just one question. how do you come up with the solutions. i have solved 400 leetcode problems. but still i find difficult to come up with this kind of solution.
It’s part of a pattern in binary search. It’s called min of max. Also there’s max of min. So those types of questions are also phrased in that way
log is square root on steroids😂
Sir please add these questions in NeetCode All Lists also .
Then it will be convenient to have all problems in one place during the revision .
yes
@@mfizt2537 obviously I know it .
But it will be more convenient if all questions are presented in one list .
@@dk4882 seconded
please explain your logic for m = l + (r - 1) // 2 instead of m = (l + r) // 2
It makes no difference in this specific situation, but if the numbers are really big, you can run into overflow problems.
for instance if r is close to int_max, and l = 1/2 int_max, l + r will be greater than max_int.
l, r = 0, max(nums)
You talking slower is so much better to absorb!
log is square root on steroids 🤣🤣🤣🤣
kinda a hard problem tbh
Agreed, especially the optimal solution
I have attempted the solution below around 10 times. Time Limit exceeded on every attempt. I have reviewed over and over and can see absolutely no difference from your code.
class Solution:
def minimizeMax(self, nums: List[int], p: int) -> int:
def isValid(threshold):
i, count = 0, 0
while i < len(nums) - 1:
if abs(nums[i] - nums[i+1])
reverting your (l+r) // 2 change ran without issue. Confused as to how you got 100% passed on this as I had no luck after many submission attempts.
10 ** 9 is cringe, you can't do in a real interview. so why do you show this? you should use right = nums[n - 1] - nums[0]
I don't get why scanning through the sorted array comparing each neighbours difference with a previously stored "min_value" shouldn't work... It's O(n)
The minimum distance of a value with a neighbour could fall on either side of it , which we are not sure about,
@@user-le6ts6ci7h Yeah, but if we compute the difference between the ith and i+1th elements of the array and take the minimum value between that difference and the "min_malue " you should check on either side of the number.
In the case of [1, 2, 4] you check 1-2 when i = 1, and 2-4 when i = 2
Yeah ,I got you, but , keeping on updating the minimum variable doesn't help us, this is right approach , if you have been asked to find the minimum difference between any single pair , but the question is to minimum diff, and you must choose p pairs , not one, I hope this helps
@@user-le6ts6ci7hOh that was the missing piece, thanks!!
I guess that to extend my solution to have multiple pairs we could use a min heap to store n lowest values then!