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?
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
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
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.
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.
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
*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
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.
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
@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.
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
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());
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!
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?
Another way
```
for num in nums:
# Update smallest elements
if num = largest[3]:
largest[3] = num
largest.sort(reverse=True)
```
similar idea :
class Solution {
public:
int minDifference(vector& nums) {
int n=nums.size();
if(n
same code i developed in java!
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
"Solution to the most hardest part of this problem is simple, just use a built-in python library"
Amazing explanation 👏 -.-
Why not just?
fun minDifference(nums: IntArray): Int {
if(nums.size
Great explanation as always. Thank you
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!
the video and the explaination is awsome..but could you try to code in java or c++
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
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
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.
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.
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)
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
@@notcountdankula The initial heapify is O(n) and popping 4 times takes 4 * O(log n). So, O(n) in total
oh first haha. I appreciate you Neet
brilliant
multiple choice problem detected brute force selected 🗿
I think the question should be more clear and provide more details
*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
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.
Nice🎉🎉
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
difficult to come up with the intuition here.
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
Just wanted to say I love you bro you're awesome
Love you too ❤️
@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
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());