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

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: www.linkedin.com/in/navdeep-singh-3aaa14161/
🐦 Twitter: neetcode1
⭐ BLIND-75 PLAYLIST: kzbin.info/www/bejne/gX3PiXZ8fJqHpKM
Problem Link: leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/description/
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

[@utkarshdewan8736]

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

[@woodylucas]

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

[@chrischika7026]

skill issue.

[@notcountdankula]

Cheat code in which way? Easy syntax?

[@chrischika7026]

@@notcountdankula yup and it just looks clean

[@aashishbathe]

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

[@MP-ny3ep]

Great explanation as always. Thank you

[@kareni7572]

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

[@LasTCursE69]

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

[@CuriousAnonDev]

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

[@tirasjeffrey2002]

one day at a time man, no shame in accepting u cant come up with the solution, how else do we increase our knowledge

[@joaopedrocastro4486]

its okay bro, just have pacience and try to solve it, if you cant just look a solution and try to solve it another day!

[@puneettripathi8418]

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?

[@HuyLe-zx8ko]

brilliant

[@chien-yuyeh9386]

Nice🎉🎉

[@kennycarneal3577]

Just wanted to say I love you bro you're awesome

[@NeetCodeIO]

Love you too ❤️

[@Anthony-oz1jc]

similar idea : class Solution { public: int minDifference(vector& nums) { int n=nums.size(); if(n

[@johnniewalkerjohnniewalker2459]

same code i developed in java!

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

[@MykolaPavluchynskyi]

Sorry, it's not actually true, it was because of not optimal updates in heaps, but always adding and removing extra. With extra checks for avoiding non efficient poll/offer - it is actually faster

[@adityabhatt4177]

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

[@tirasjeffrey2002]

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

[@HuyLe-zx8ko]

he means we don't need to care about those

[@dss963]

When the lower one incremented to next high or higher element to next lower , there is no point of considering it as we care about diff b/w high and low

[@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.

[@business_central]

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

[@mayursmahajan]

It would have been nlogn if we sorted nums. We are not sorting nums but sorting a sub arr of size 4 that we got from the heap. Thus their sorting will be considered as Constant time

[@business_central]

@@mayursmahajan Thank you very much! Now I get it! Thanks!

[@notcountdankula]

​@@mayursmahajanbut we are heapifying the entire array. So it will take nlogn anyways

[@tarekradwan8661]

The question is not removing could you pleaSe fix that. I know it is still the same but just confuses

[@pastori2672]

multiple choice problem detected brute force selected 🗿

[@roderickli6505]

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

[@chrischika7026]

its only 4 elements so its O(N)

[@shnorlaxzz395]

I think the question should be more clear and provide more details

[@MrSpeedFrk]

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

[@samridhshubham8109]

Wer u able to understand? Or need help?

[@bullyversal5313]

Nah I think it's pretty much understandable

[@chrischika7026]

nah its lightwork

[@antondonohue8943]

oh first haha. I appreciate you Neet

[@olegleonov1310]

Why not just? fun minDifference(nums: IntArray): Int { if(nums.size

[@bundiderp5109]

It's a bit unfortunate that you jumped right in with the intention to REMOVE elements. The description says "change to any value". The observation that this is effectively the same as removing was not made in the video, but beforehand.

[@edmonddantes587]

difficult to come up with the intuition here.

[@pranithtirumalsetti1453]

I am waiting for you from 1 hour

[@tirasjeffrey2002]

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

[@shwethaks7994]

@NeetCodeIO can you make a video on giving tips regarding job search and some websites where we can apply. I think this would be very helpful to many people like me in the middle of a job hunt.

[@MWKING]

The video is speeded-up by default

[@dheereshagrwal]

*no need to sort bud* min_four = nsmallest(4, nums) max_four = nlargest(4, nums) res = float("inf") for i in range(4): res = min(res, max_four[4 - i - 1] - min_four[i]) return res

[@akialter]

Man coding in a language that doesn't have min or max heap is tricky, probably just sort the array and call it a day Edit: can implement quickselect which average O(n), and a good segway to LC 215 kth largest element in array

[@bhavyajainnd]

What's the Java equivalent fo heapq.nsmallest and largest?

[@akshatsingh6036]

implement it yourself LOL

[@f840810]

You really need to use priority queue to implement that equivalent function. Yet, you can use two arrays and some element comparisons to determine the biggest and smallest 4 elements

[@RuslanZinovyev]

For minHeap it should be something like this: Queue minHeap = new PriorityQueue(Comparator.naturalOrder()); For maxHeap: Queue maxHeap = new PriorityQueue(Comparator.reverseOrder());