Minimum Difference Between Largest and Smallest Value in Three Moves - Leetcode 1509 - Python
Вставка
- Опубліковано 16 лип 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/minimum...
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 - Наука та технологія
That was so bloody clever. I just learnt heap a week ago and did not even think that we can use a heap here
Awesome man. Learnt something new today. Nsmallest and nlargest. Thank you!
Great explanation as always. Thank you
Thanks for showing us previous attempts!
Good explanation & 2nd solution was interesting...
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?
Python is such a cheatcode it is ridiculous, and it isn't even fair 🤕
skill issue.
Cheat code in which way? Easy syntax?
@@notcountdankula yup and it just looks clean
na bro i am so done
i cant fucking solve these questions no matter how much i try shit
one day at a time man, no shame in accepting u cant come up with the solution, how else do we increase our knowledge
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!
Nice🎉🎉
brilliant
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
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
similar idea :
class Solution {
public:
int minDifference(vector& nums) {
int n=nums.size();
if(n
same code i developed in java!
the video and the explaination is awsome..but could you try to code in java or c++
"Solution to the most hardest part of this problem is simple, just use a built-in python library"
Amazing explanation 👏 -.-
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.
Just wanted to say I love you bro you're awesome
Love you too ❤️
by remove, he means setting it to the min value right? coz you cant actually remove, you can only change it to any val
he means we don't need to care about those
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
The question is not removing could you pleaSe fix that. I know it is still the same but just confuses
can someone clarify further why the sorted in the heaps solutions? doesn't adding the sorting will end us at nlogn ?
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
@@mayursmahajan Thank you very much! Now I get it! Thanks!
@@mayursmahajanbut we are heapifying the entire array. So it will take nlogn anyways
I think the question should be more clear and provide more details
Why not just?
fun minDifference(nums: IntArray): Int {
if(nums.size
multiple choice problem detected brute force selected 🗿
is heap actually a N operation? i feel like its not and when i view the time complexity on leetcode its n lgn
its only 4 elements so its O(N)
difficult to come up with the intuition here.
oh first haha. I appreciate you Neet
I guess I'm the only one that found this explanation confusing sigh
Wer u able to understand? Or need help?
Nah I think it's pretty much understandable
nah its lightwork
The video is speeded-up by default
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
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.
@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.
I am waiting for you from 1 hour
*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
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
What's the Java equivalent fo heapq.nsmallest and largest?
implement it yourself LOL
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
For minHeap it should be something like this: Queue minHeap = new PriorityQueue(Comparator.naturalOrder());
For maxHeap: Queue maxHeap = new PriorityQueue(Comparator.reverseOrder());