Epic dedication brother... First I saw your Maximum product of word length solution (27 may) then N queens 2 and now today... I saw your github profile... Your consistency is just on another level... Ab toh bhai question dekh ke algo ka yaad aajata hoga aapko!!
@@CodeWithSunchitDudeja suppose 1 backet contains two value min and max value whose difference is max(max gap).....u are considered this case....plz help me
Great explanation for this difficult question! Honestly I can't think of ways I can solve it since I know little about the pigeon hole theory. It looks more like a math problem than coding problem to me.
if you replace 21 with 17, and 25 with 28, the bucket for 17 remains same at 2, bucket for 28 remains same at 3, and bucket 1 remains empty. But the answer changes to being obtained from two adjacent buckets, #2 and #3 and not #0 and #2 ie the two buckets that skipped an empty bucket in between. so how did the pigeon hole thing help?
waiting for todays problem !! search suggestions system , did it using trie , but apparently there are more optimal ways to do it (and i cant wrap my head around those :P )
Honestly, it was one of the contest that this question came. I could not solve it then although I was aware of pigeonhole. Then I solved it, so that it somewhere in my head how to go about it. These kind of questions are very difficult to come up with in interviews if you have not solved them before, as they require special tricks to get solved.
Ceil((max - min / (n - 1)) provides the maximum gap in a scenario where all elements are evenly spaced. If any elements (other than max and min) were shifted in either direction, the max gap would only grow. Thus, there can be no max gap smaller than the max gap for evenly spaced elements.
Bro what if there are 2 copies of max element in the array...then how will be the bucket of that element will be found? Because we arr taking only open interval at the closing side
if we create a big array and place number according to their index for ex 3,6,9,1 for this our array will look like 0,1,0,3,0,0,6,0,0,9,0,0..... and we simply ignore 0 and find the difference ?
@Coding Decoded , can you please explain me by the last bucket will never be empty , since ans will come from right and left side of the empty bucket , this means 1st bucket and last bucket is never empty , can you please explain me this ???????????
Bro everything is well explained can you please tell why did we ignore max and min and why did we choose n-1 buckets and n-2 elements what about one empty bucket?
You can include min, max in n-1 buckets but there is no use, because min value will be in first bucket, max value is in last bucket, while calculating gap b/w two index we need max value of first and min value of 2nd, min is always min for first and wise versa for max
@@CodeWithSunchitDudeja Thanks, This video has best explaination. Finally able to solve, but still one question remains - "How to identify if pegionhole principle applies to the problem"
Bro i've solved this question by my own and got your videos notification so i thought lets have a look but the way thought is totally different i didn't even know that it comes under pegion hole principle. I think this question should not be considered in hard problem its must be in easy section.
Thank you for drawing everything out, makes it much easier to understand
Good to hear that
Great explanation! Clearly understood the approach. Thanks a lot!
Epic dedication brother... First I saw your Maximum product of word length solution (27 may) then N queens 2 and now today... I saw your github profile... Your consistency is just on another level... Ab toh bhai question dekh ke algo ka yaad aajata hoga aapko!!
Most welcome Akshay, haha
@@CodeWithSunchitDudeja suppose 1 backet contains two value min and max value whose difference is max(max gap).....u are considered this case....plz help me
I understand that why are u taken this case....bcz alteat 1 backet is empty
@@CodeWithSunchitDudeja can u share ur LinkedIn Profile
@@saunaknandi1814 Linkedin: bit.ly/3n65udU this is of Coding Decoded, my personal is www.linkedin.com/in/sunchitdudeja/
Great explanation for this difficult question! Honestly I can't think of ways I can solve it since I know little about the pigeon hole theory. It looks more like a math problem than coding problem to me.
if you replace 21 with 17, and 25 with 28, the bucket for 17 remains same at 2, bucket for 28 remains same at 3, and bucket 1 remains empty. But the answer changes to being obtained from two adjacent buckets, #2 and #3 and not #0 and #2 ie the two buckets that skipped an empty bucket in between. so how did the pigeon hole thing help?
Thank You So much you cleared this concept 🙏👍
at 12:22 the line 41 to 48 is confusing. we just need maxOfBucket[i] - minOfBucket[i] and compare it with the current max value, right?
Hlw
waiting for todays problem !! search suggestions system , did it using trie , but apparently there are more optimal ways to do it (and i cant wrap my head around those :P )
Isn't N-2 confusing? What if you have multiple repeating max elements? In your example, what if you had two 49 and two 3s?
I guess duplicates are not real contender of answer , since max diff it can give is zero , so its doesn't matter
02:43 will the number of buckets always be n-1 ? if n=1000, then number of buckets will be 999?
very good and detailed explanation! Thanks!
Maza aa gaya, very clear code
How would you come up with this approach or intuition?.
Honestly, it was one of the contest that this question came. I could not solve it then although I was aware of pigeonhole. Then I solved it, so that it somewhere in my head how to go about it. These kind of questions are very difficult to come up with in interviews if you have not solved them before, as they require special tricks to get solved.
@@CodeWithSunchitDudeja Yes, that's what I was also thinking. Thanks for replying.
@@CodeWithSunchitDudeja it would be better, if you tell how did you reach upto solution in starting of the video, that'll make more sense.
maximum gap will be no smaller than ceiling[(max - min ) / (N - 1)]. , WHY??
Ceil((max - min / (n - 1)) provides the maximum gap in a scenario where all elements are evenly spaced. If any elements (other than max and min) were shifted in either direction, the max gap would only grow. Thus, there can be no max gap smaller than the max gap for evenly spaced elements.
@@garrub3991 thnx buddy
woww such a cool appraoch
can also be done in linear time and space by radix sort
totally
Bro what if there are 2 copies of max element in the array...then how will be the bucket of that element will be found? Because we arr taking only open interval at the closing side
why not use 7 buckets to contain 8 numbers? why exclude min and max
if we create a big array and place number according to their index for ex 3,6,9,1 for this our array will look like 0,1,0,3,0,0,6,0,0,9,0,0..... and we simply ignore 0 and find the difference ?
Of course you can do it but that won't work as the range of input no is 10^9. Hashing solution will cause TLE
Ohh yess .... Thanks 👍
@@CodeWithSunchitDudeja and if we have multiple min and max will it handle that case also (3,3,3,21,9,37,49,49)
@@ojasvichaudhary8724 yes it will. Run it via a test case
It's amazing you got a new subscriber
Yay! Thank you!
Why are we taking an extra bucket??
That's something bro
@Coding Decoded , can you please explain me by the last bucket will never be empty , since ans will come from right and left side of the empty bucket , this means 1st bucket and last bucket is never empty , can you please explain me this ???????????
Bro everything is well explained can you please tell why did we ignore max and min and why did we choose n-1 buckets and n-2 elements what about one empty bucket?
You can include min, max in n-1 buckets but there is no use, because min value will be in first bucket, max value is in last bucket, while calculating gap b/w two index we need max value of first and min value of 2nd, min is always min for first and wise versa for max
well in questions like these, how will i came to know about what bucket size should i take??
Bro good explanation but code thopatu example chesedi vunde code antha understand kaledu bro concept ok😢
Thnaks alot
thanks Tathagat
Nice explanaition bro
Why we skipped max and min while filling the buckets?
Because we are trying to put n-1 numbers in n-2 buckets
@@CodeWithSunchitDudeja Thanks, This video has best explaination. Finally able to solve, but still one question remains - "How to identify if pegionhole principle applies to the problem"
hi
can you please tell me why have you not considered the min and Max values of the array?
So that I can apply pigeonhole principle of placing N-2 elements in n-1 buckets.
hi let's say the Max difference is between the highest element and the second largest element. we are not comparing these values right?
Hey ! Would the use of priorityqueue be considered a valid solution here ??
Nopes it will lead to nlogn
@@CodeWithSunchitDudeja okay thanks
Hello, Can you please explain leetcode 837: New 21 game please. It will help a lot. Have tried but not getting. Thanks.
Sure I will try and have look at the question
@@CodeWithSunchitDudeja Thanks it will help a lot.
Video quality is low, can't see properly
Give it some time, TH-cam is processing it.
how is this O(n)? In worst case this is O(nlogn) only
Bro i've solved this question by my own and got your videos notification so i thought lets have a look but the way thought is totally different i didn't even know that it comes under pegion hole principle. I think this question should not be considered in hard problem its must be in easy section.
The question has a condition to be solved in O(n)
Did you just sort it ... that's funny ..