Minimize the Maximum Difference of Pairs - Leetcode 2616 - Python

[@NeetCodeIO]

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

[@thespicycabbage]

not all heroes wear capes

[@crossvalidation1040]

Great video! Could you please also share the DP solution for this one?

[@sumitsharma6738]

You can upload your other videos that you say on podcast that I have a bunch of recorded videos to upload!!

[@MP-ny3ep]

Yes, please continue with the daily leetcode problems. It's so helpful

[@tianmingguo8271]

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.

[@michael._.]

*log is square root on steroids* - I can never forget this now

[@hengyulee4319]

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.

[@tirthajrikame1052]

Nice catch!

[@DanielRodrigues-bx6lr]

And since you've sorted the array, might as well just take the difference of (last element - first element).

[@hengyulee4319]

@@DanielRodrigues-bx6lrexactly

[@tirthajrikame1052]

@@DanielRodrigues-bx6lr yeah! I did the same thing, and this tweak made my code faster than 90%

[@uptwist2260]

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

[@michelle_tsai_drums]

lol "log is square root on steroids" brilliant solution with clear explanation as always, plz keep these daily challenges coming

[@animesekai4229]

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.

[@panzach]

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

[@FluteVJ]

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.

[@sumitsharma6738]

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;

[@GuruPrasadShukla]

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

[@vaishnavisahu3167]

Hi there, please provide the dynamic programming solution also. (code reference or similar question solution will also work). Thanks!

[@PabloEscobaro-jf8ib]

Constraints: 0

[@GuruPrasadShukla]

lots of support from india

[@vs3.14]

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?

[@sumitsharma6738]

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;

[@dineshrajant4000]

Can you explain that mid pointer why l + (r-l)/2 is preventing overflow

[@ChrisCox-wv7oo]

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

[@deathbombs]

The alternative is using r+l /2. The r+l piece can over flow

[@indraxios]

this should be a hard level question

[@oksowhat]

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

[@gouthamp9066]

can we have a feature to take only required courses from the website instead everything

[@rudrakhare1158]

# Special case when p is 0 if p == 0: return 0

[@utkarshsinh1919]

It's great to see you back!

[@suryakantadey717]

why not take the max till max value in the array ?

[@ronbuchanan5432]

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

[@mehdisaffar]

same question here

[@bossmusa9075]

how can i be like you man, you are like genius or smth

[@akankshasharma7498]

idk why.... I am never able to solve problems like these by myself 😞

[@yaswanth8973]

It needs lots of understanding and practice

[@rustamkarimov1191]

l, r = 0, max(nums)

[@lucifersenpai1948]

please explain your logic for m = l + (r - 1) // 2 instead of m = (l + r) // 2

[@acidtoe1278]

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.

[@GuruPrasadShukla]

log is square root on steroids😂

[@m3hdim3hdi]

please someone give us the dynamic programming solution in python please

[@vanshrodge7670]

The way he says log is sqare root on steroids🤣

[@adilkhatri7475]

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.

[@kareni7572]

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

[@krateskim4169]

Great video man

[@yeah5037]

You talking slower is so much better to absorb!

[@jessanraj9086]

Great video

[@dk4882]

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 .

[@metarus208]

yes

[@dk4882]

@@mfizt2537 obviously I know it . But it will be more convenient if all questions are presented in one list .

[@metarus208]

@@dk4882 seconded

[@pradipakshar]

log is square root on steroids 🤣🤣🤣🤣

[@metarus208]

kinda a hard problem tbh

[@NeetCodeIO]

Agreed, especially the optimal solution

[@name_surname_1337]

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]

[@j_curlin]

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

[@j_curlin]

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.

[@doombringer1810]

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)

[@user-le6ts6ci7h]

The minimum distance of a value with a neighbour could fall on either side of it , which we are not sure about,

[@doombringer1810]

​@@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

[@user-le6ts6ci7h]

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

[@doombringer1810]

​@@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!