Minimum Difference Between Largest and Smallest Value in Three Moves - Leetcode 1509 - Python

0:00 - Read the problem
0:30 - Drawing Explanation 1
5:39 - Coding Explanation 1
8:11 - Drawing Explanation 2
12:26 - Coding Explanation 2

leetcode 1509

#neetcode #leetcode #python

[utkarshdewan]

That was so bloody clever. I just learnt heap a week ago and did not even think that we can use a heap here

[aashishbathe]

Awesome man. Learnt something new today. Nsmallest and nlargest. Thank you!

[codewithmePuneet]

doesn't heapifying an array of size n, itself is a process of O(n*log(n)), you perform sink and swim operations that both take O(log(n)) for n elements?

[kareni]

Thanks for showing us previous attempts!
Good explanation & 2nd solution was interesting...

[woodylucas]

Python is such a cheatcode it is ridiculous, and it isn't even fair 🤕

[Blu]

similar idea :
class Solution {
public:
int minDifference(vector<int>& nums) {
int n=nums.size();
if(n<5) return 0;
sort(nums.begin(), nums.end());
int res = min({
nums[n-1] - nums[3],
nums[n-4] - nums[0],
nums[n-2]- nums[2],
nums[n-3]- nums[1]}
);
return res;
}
};

[LasTCursE]

"Solution to the most hardest part of this problem is simple, just use a built-in python library"

Amazing explanation 👏 -.-

[MP-nyep]

Great explanation as always. Thank you

[tirasjeffrey]

by remove, he means setting it to the min value right? coz you cant actually remove, you can only change it to any val

[MykolaPavluchynskyi]

Interesting that if you try to do in java with heaps - it will be more than twice slower. Because with sorting it can be done on int[], without using a collections with all their overhead

[roderickli]

is heap actually a N operation? i feel like its not and when i view the time complexity on leetcode its n lgn

[business_central]

can someone clarify further why the sorted in the heaps solutions? doesn't adding the sorting will end us at nlogn ?

[ajohnson]

Not entirely sure I even understand the problem, but it seems to me using a vector in C++ can do it all with sort and erase followed my just accessing the first and last elements for the difference.

[olegleonov]

Why not just?
fun minDifference(nums: IntArray): Int {
if(nums.size <= 4) return 0

nums.sort()

var res = Int.MAX_VALUE
for(i in 0..3) {
res = minOf(res, abs(nums[i] - nums[nums.lastIndex - (3 - i)]))
}
return res
}

[CuriousAnonDev]

na bro i am so done
i cant fucking solve these questions no matter how much i try shit

[adityabhatt]

the video and the explaination is awsome..but could you try to code in java or c++

[RuslanZinovyev]

Logically, the solution was obvious but it would take me a lot of time to come up with this: int right = nums.length - 4 + left;
btw is it really necessary to sort Heaps? It is supposed to be in the right order out of the box.

[tirasjeffrey]

if you think neet's way of using hardcoded numbers is hard to wrap your mind around, try this:
n = len(nums)
i = 0
j = 3

if len(nums) <= 4:
return 0

nums.sort()

diff = float('inf')

while i <= 3 and j >= 0:
diff = min(diff, nums[n - 1 - j] - nums[i])
i += 1
j -= 1

return diff

-> i will go from 0 to 3, j will go from 3 to 0
-> i will be the left pointer, ie number of values cut off from the left
-> j will be the right pointer, ie number of values cut off from the right
-> thru this, we can get 4 combinations of removals:
=> 0 values from left, 3 values from right
=> 1 value from left, 2 from right
=> 2 from left, 1 from right
=> 3 from left, 0 from right
return the min among these calculations

hope this helps those who couldnt grasp neet's explanation

peace, x

edit: i had no clue heap could be used here im dumb asf

[pastori]

multiple choice problem detected brute force selected 🗿

[MrSpeedFrk]

I guess I'm the only one that found this explanation confusing sigh