Table of Contents: The Problem Introduction 0:00 - 1:33 Why Not Just Sort It? 1:33 - 2:08 Investigating How We Can Actually Use K 2:08 - 3:22 Expressing The Exhaustive Set of Possibilities 3:22 - 5:57 Analyzing The Critical Information 5:57 - 7:17 We Begin Doing Placements 7:17 - 10:51 Time Complexity 10:51 - 12:47 Space Complexity 12:47 - 13:27 Wrap Up 13:27 - 14:05 The code for the problem is in the description. Fully commented for teaching purposes.
I am not that good with heap sorting plus O(Nlog(N)) time is taken . If we trade space for time, maybe it can be done in linear time. First make a new array of size maximum value of given array and then count no. of times values appear in given array and place at same index as value in new array. After that just use new array and place the value in sorted manner. idk its right or not. i m still trying,i got this question yesterday in my pramp interview.
@@BackToBackSWE I edited little bit of my algorithm and its works fine with array which is not having large max value, but it take a little bit more time than heap sort. But I recently found about Radix sort and Count sort and they are perfect for this question . As I am a beginner , I am learning slowly slowly. And I m grateful you replied me, Thank you. Its really motivating.
I was just reading EPI, and I have seen this problem on the Heaps section. After a few good minutes, I realised I was hopeless, so I decided to search it on youtube. I did not believe I would have much luck. You can not imagine how relieved and excited I was when I saw that YOU (my favourite person on TH-cam :)))) made a video on this exact topic.
Wow I just discovered your channel, it's awesome ! Your videos are amazing ! I may not need it now but one thing is sure, I will subscribe to remember where to go when I need it
Your videos are awesome,sir.I subscribed to your channel as soon as i listened to your way of explaining.Please keep making videos,your way of teaching is infinitely times better than my college professors
me too - the interview was for mostly a frontend role but the last challenge was like a backend challenge....this problem was given and i died. knowing now to use a min heap would have definitely helped! oh well we will know for next time! here's my code (js): let unsorted = [3, 2, 1, 5, 6, 4] let kSorted = (arr, k) => { let minHeap = arr.splice(0, k + 1) let sorted = [] while (arr.length || minHeap.length) { while (minHeap.length) { let min = getMin(minHeap) sorted.push(min[0]) minHeap.splice(min[1], 1) } minHeap = arr.splice(0, k + 1) } return sorted } let getMin = (arr) => { let min = [Infinity, null] for (let i = 0; i < arr.length; i++) { let curr = arr[i] if (curr < min[0]) { min[0] = curr min[1] = i } } return min } console.log(kSorted(unsorted, 2))
your concepts are really very clear ! such a nice explanation dude ! you actually made it look very easy!the best part was that you described the whole process of how to start thinking for this question ! thanks man !
Great video Ben, but I had one question. Ultimately, the time complexity comes out to be O(n log(k)) using heaps, but if we were to just opt with sorting the array as is, with merge sort for example, we would get O(n log(n)). How exactly is it, that just outright sorting the array would prove to be significantly worse than the solution you posed? Is it just in the case when N grows exponentially larger? As I would assume that K would just remain constant(relative to a specific problem i.e. k=3, k=4, etc.)? Thanks, bru.
It may not be significantly worse asymptotically since the 2 bounds are very similar (a linear factor multiplied by a logarithmic factor). It'd be interesting to see the graphs of work on random sets of calls with exponentially large n and k. The tail behaviour would look pretty similar, but this is like comparing y = 100n to y = n, the first function is objectively slower...but it is linear...both are linear. Just because both bound and will have the same shape of graph, doesn't mean that one may not be much much faster with large inputs. Asymptotic measures look at graph behaviour (think of shape) and nothing concrete.
Amazing video. Thanks, please keep making such kind of videos. It helped me to understand this algorithm. I was thinking about why we are taking k+1 heap but you have explained it very well. Thanks.
Awesome explanation! I wonder when the k == n.length, it is best to just run a quick sort and save some space? Since quicksort will be in-place (or in worst case O(log n) space as the time complexity will be same as the heap sort.
Yeah I think? I'm fuzzy on this problem's description, solutions, etc. but yeah one can do internal optimization like that. The worst case will still rule though.
I actually got this problem as my problem for my Twitch Technical phone interview which I messed up really badly. I came up with a brute force solution but I ran out of time before I could really optimize it. But then again a heap never came to mind when I was thinking through it.
Yeah, it happens. Speaking of coincidences, we got a practice exam for my (actual) algorithms exam that is happening tomorrow and this same question was on the practice exam. I didn't even mean for that to happen. Wild
Really enjoyed this one, especially the stacking of solutions per index of the possible solution and seeing the binary heap and complexity classes for time/space.
What are some examples of when you would use this algorithm in real life? I can't think of what sort of situation you would have where you would be given a k-sorted array to begin with or how that k-sorted array would be generated in the first place. Any ideas?
Thank you for your hard work on those videos. What do you think about doing an episode about dynamic programming? Explain top down and bottom up approaches, dp table method, how to approach it in general etc.
I understand that its almost sorted and hence using the Heap Sort. Since it's no ,can't we try Counting sort? It will be O(n+k) faster than the approach?
Next time can you make sure your biceps aren't blocking view of the board. Thanks. For real though, this is an awesome explanation of the problem, and how to arrive at the solution. Most of these channels skip the thought process behind solving the question, and it's that type of critical thinking that will help people in their interview - not just memorizing algorithms. Thanks mate, keep up the good stuff!
I sort of know what you are saying. Why a dequeue? Even if we maintain the smallest element, how are you cognizant of its position in the underlying structure for removal at all times? Elaborate a little and analyze each operation, I'm interested.
@@BackToBackSWE I don't believe a sliding window will work here. This is because we need to always maintain the ordering of the elements to get the smallest value every time
Hey man. Awesome video. probably the best placement-prep channel on youtube. like when you made that diagram, before you mentioned heap, heap popped into my mind and i paused the video and came up with the solution. initially when i saw the problem, i had no clue how this was going to happen. Anyway I have a major doubt tho. Where can I learn the analysis of time and space complexities for all kinds of loops, recursion,divide conquer etc.
haha nice! That is so cool. And for time complexities... :) I'm making this twitter.com/thebigoguide, it'll be out the end of July. It's why I've been so quiet for so long on the channel
No question is silly, the only similarity is the data structure used to sort. If k=n then yes, this is basically heapsort where all items enter the heap and are placed out. But heapsort only uses the sift up subroutine in the initial build heap phase before the placement phase, and it only sifts up the first n/2 items one by one.
I was reviewing the code you put in the description. It makes sense for the most part, but why did you make it such that the min heap has k + 1 elements at any time instead of just k elements?
@@BackToBackSWE I watched the video before the comment. I think I got it since I have had a night's sleep. I think it is because we include the first element plus the k elements to the right.
Ben, great videos! I have been watching tons of your videos and it has helped me a lot! I have a quick question about this problem. Will bubble sort be a good strategy here? I feel like in this particular case bubble sort will have a time complexity of O(k*n) = O(n). Please correct me if I'm wrong.
@@BackToBackSWE In this case, to sort this array we would have to traverse it at most k times with bubble sort. I haven't actually worked it out so I may be wrong.
Can please make videos mainly on backtracking, greedy, dynamic programming .. it will helpful ..because most people find those problem difficult to solve. Thanks
hey bro i'm here from your solutions on leetcode(minimum window susbstring):- even though approach of your videos is good i think company wise questions approach would be better . for eg :- take all uber questions , then amazon etc . this covers the most asked ones and all the common interview questions irrespective of the company . hope i made sense . cheers .!
Yes, this is something I pondered when I started this channel. How would I format things. The thing is...I didn't think that that would be a good choice...to revolve a whole channel and movement around company specific questions....although it does align with the mission of the project (to get people jobs)...I just don't think it'd be a good idea to pander to the idea that companies ask a certain set of questions (although some DO do that) as a long-term content strategy. It'd certainly get the channel WAY more views and give it a viral aspect but... What if a company stops asking a question? What if they stop using these kinds of questions all together? A more stable idea in my belief is to revolve the channel around classes of problem and the fundamentals that guide each problem class. I think anyone can look up the company lists and then do those problems and then...yeah I may just be straight wrong but eh...
There is no guarantee that Amazon asks X, Google asks Y, etc. Interviewers at these companies are allowed to choose whatever question they want to ask, so it is possible (or even probable) that you could get a Facebook question at Google, a Palantir question at AirBNB, etc.
This is actually the solution to a slightly different interview problem: k-left sorted array where elements cannot move left more than k positions. In you case the restriction is on both directions so it’s more complicated and your solution doesn’t work. Imagine the first element in your array is the biggest (10). It’ll stay in the min heap all the way to the end and will end up as the last one in the final array so it’d move more thank k=3 positions to the right
"Imagine the first element in your array is the biggest (10)". In the video example the first element cannot 10. The only possible positions that 10 can end up if in a final sorted arrangement (as in the video example): k = 3 arr = [ 6, 5, 3, 2, 8, 10, 9 ] are [ x, x, 10, x, x, x, x ] (3 to left) [ x, x, x, 10, x, x, x ] (2 to left) [ x, x, x, x, 10, x, x ] (1 to left) [ x, x, x, x, x, 10, x ] (0 change) [ x, x, x, x, x, x, 10 ] (1 to right) "It’ll stay in the min heap all the way to the end and will end up as the last one in the final array so it’d move more thank k=3 positions to the right". k cannot be 3 if the 10 is in first position (index 0). What am I missing? I am confident that this is correct, but I may be wrong. - Ben
@@zdanodron Yes, that input is invalid is what I mean. 10 can't be there or else it breaks the problem description since it will be 6 positions from its "final resting place". Does that make sense? It does not conform to the fundamental problem description that allows the approach to work in the first place. The heap approach SHOULDN'T work for that input because of the very nature of it. It breaks our fundamental assumption about the possibilities at any one index. (the elimination we do in the video)
Back To Back SWE Fair enough. After reading the problem description again, I find you are correct indeed. I’ve got confused because once I was asked a similar question to produce a K -sorted array for an arbitrary input
@@zdanodron No problem, it is no biggie. Glad I cleared it up, I got worried for a second 😅 Keep asking great questions, I'm happy you are challenging things. Continue. It is the sign of a great learner to challenge what they know and make these connections.
There is a better way actually, build heap for first k+1 elements which takes O(k) time, and then do the operations for the remaining elements which would take O((n-k)(logk)), the total time complexity would be O(k+(n-k)logk) which is better than O(nlogk)
For anyone looking for a code implementation can look at the link below. Hope this helps. I took this video as a reference for the code and also commented where it was required. pastebin.com/2xRuGeAi
Table of Contents:
The Problem Introduction 0:00 - 1:33
Why Not Just Sort It? 1:33 - 2:08
Investigating How We Can Actually Use K 2:08 - 3:22
Expressing The Exhaustive Set of Possibilities 3:22 - 5:57
Analyzing The Critical Information 5:57 - 7:17
We Begin Doing Placements 7:17 - 10:51
Time Complexity 10:51 - 12:47
Space Complexity 12:47 - 13:27
Wrap Up 13:27 - 14:05
The code for the problem is in the description. Fully commented for teaching purposes.
I am not that good with heap sorting plus O(Nlog(N)) time is taken . If we trade space for time, maybe it can be done in linear time. First make a new array of size maximum value of given array and then count no. of times values appear in given array and place at same index as value in new array. After that just use new array and place the value in sorted manner. idk its right or not. i m still trying,i got this question yesterday in my pramp interview.
hows it going with the question now
@@BackToBackSWE I edited little bit of my algorithm and its works fine with array which is not having large max value, but it take a little bit more time than heap sort. But I recently found about Radix sort and Count sort and they are perfect for this question . As I am a beginner , I am learning slowly slowly. And I m grateful you replied me, Thank you. Its really motivating.
The way you approach a problem is exactly how the things should be taught. I wish i had find you earlier.
thanks haha
@@BackToBackSWE Thanks so much you are just awesome
The best video on this problem. Everyone just explains how to use heap, but you explained why we need to use heap.
The way you explain the problems and make the viewers to think critically is amazing. 👍 Thank you
sure.
I was just reading EPI, and I have seen this problem on the Heaps section. After a few good minutes, I realised I was hopeless, so I decided to search it on youtube. I did not believe I would have much luck. You can not imagine how relieved and excited I was when I saw that YOU (my favourite person on TH-cam :)))) made a video on this exact topic.
glad you found us
Just wow. This is how intuition should be explained. Subscribing now.
I know I am 5 years late but you're the goat
worth watching, best video ever
You not only give the solution of the problem but show us the path to get that approach of finding a solution
yeah thanks
Best explanation I found on TH-cam
Wow I just discovered your channel, it's awesome ! Your videos are amazing ! I may not need it now but one thing is sure, I will subscribe to remember where to go when I need it
thanks! I appreciate it!
This is awesome. You're a wonderful wonderful teacher. Clear and Concise. Please do more of these videos.
ok, on it chief
The way you explain stuff from a beginners perspective is really intuitive. Keep up the awesome work. Looking forward to more of your stuff!
thanks yo
I just got this question on Pramp yesterday and was so stuck! Happy to have found your channel :)
haha I got it on Pramp too - welcome
Your videos are awesome,sir.I subscribed to your channel as soon as i listened to your way of explaining.Please keep making videos,your way of teaching is infinitely times better than my college professors
thanks!
Super underrated, love your mindset to understand intuitions!
One of the best video i have ever seen I really wanna say thank you from bottom of my heart 💯
sure!
This channel is a gem
nah, u a gem
Today, I died on this one at my interview...should have been here yesterday.
dang
me too - the interview was for mostly a frontend role but the last challenge was like a backend challenge....this problem was given and i died. knowing now to use a min heap would have definitely helped! oh well we will know for next time!
here's my code (js):
let unsorted = [3, 2, 1, 5, 6, 4]
let kSorted = (arr, k) => {
let minHeap = arr.splice(0, k + 1)
let sorted = []
while (arr.length || minHeap.length) {
while (minHeap.length) {
let min = getMin(minHeap)
sorted.push(min[0])
minHeap.splice(min[1], 1)
}
minHeap = arr.splice(0, k + 1)
}
return sorted
}
let getMin = (arr) => {
let min = [Infinity, null]
for (let i = 0; i < arr.length; i++) {
let curr = arr[i]
if (curr < min[0]) {
min[0] = curr
min[1] = i
}
}
return min
}
console.log(kSorted(unsorted, 2))
your concepts are really very clear ! such a nice explanation dude ! you actually made it look very easy!the best part was that you described the whole process of how to start thinking for this question ! thanks man !
Hahaha I don make it look easy but all these videos are prepared and staged almost....like I'm just a normal dude haha
Best channel I've found so far....you really made my brain absorb this challenges the right way.....keep up the great job buddy
thanks, will do
Awesome explanation! The best I've seen on TH-cam.
thanks
deeply explained.....good job
thanks.
Very nice explanation. With that explanation, implementation was very easy. Thumbs up !!
thanks 🌽🚜🌽🌽
Great video Ben, but I had one question. Ultimately, the time complexity comes out to be O(n log(k)) using heaps, but if we were to just opt with sorting the array as is, with merge sort for example, we would get O(n log(n)). How exactly is it, that just outright sorting the array would prove to be significantly worse than the solution you posed? Is it just in the case when N grows exponentially larger? As I would assume that K would just remain constant(relative to a specific problem i.e. k=3, k=4, etc.)? Thanks, bru.
It may not be significantly worse asymptotically since the 2 bounds are very similar (a linear factor multiplied by a logarithmic factor). It'd be interesting to see the graphs of work on random sets of calls with exponentially large n and k. The tail behaviour would look pretty similar, but this is like comparing y = 100n to y = n, the first function is objectively slower...but it is linear...both are linear.
Just because both bound and will have the same shape of graph, doesn't mean that one may not be much much faster with large inputs. Asymptotic measures look at graph behaviour (think of shape) and nothing concrete.
Great explanation, if we do this way in an interview, selection is 100%
ye
Amazing video. Thanks, please keep making such kind of videos. It helped me to understand this algorithm. I was thinking about why we are taking k+1 heap but you have explained it very well. Thanks.
ok
You are amazing. Such a great communicator. And such an awesome thing to make these videos.
thanks
You are an awesome teacher! Keep doing great work! God bless!
Discovered your channel yesterday. Great job.
Love how you explain on how to approach the problem.
nice, welcome
Awesome explanation! I wonder when the k == n.length, it is best to just run a quick sort and save some space? Since quicksort will be in-place (or in worst case O(log n) space as the time complexity will be same as the heap sort.
Yeah I think? I'm fuzzy on this problem's description, solutions, etc. but yeah one can do internal optimization like that. The worst case will still rule though.
extraordinary explanation.. need more videos like this sir.
coming right up
I actually got this problem as my problem for my Twitch Technical phone interview which I messed up really badly. I came up with a brute force solution but I ran out of time before I could really optimize it. But then again a heap never came to mind when I was thinking through it.
Yeah, it happens. Speaking of coincidences, we got a practice exam for my (actual) algorithms exam that is happening tomorrow and this same question was on the practice exam. I didn't even mean for that to happen. Wild
Really enjoyed this one, especially the stacking of solutions per index of the possible solution and seeing the binary heap and complexity classes for time/space.
Thanks for the video! Great thought process building upto the optimal solution!
wassup, thanks
Great intuition building exercise , thank you very much
You are even better than the geeks for geeks. If I got a job I will definitely donate you my guru Dakshina (my money) By the Way I am from India lol
hahahaha nice, wassup, one world
This is a very good way to explain the heap approach.
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Amazing explanation. Very good work.
thanks
This explanation was brilliant.
Thanks
How did you record your voice during this video? Lavalier? Boom mic? The quality is great.
Beautifully Explained thanks please bring some dp questions too for interview preperation
Ok, I'll cover a lot here: , this is the site I'twitter.com/thebigoguidem working on
What are some examples of when you would use this algorithm in real life? I can't think of what sort of situation you would have where you would be given a k-sorted array to begin with or how that k-sorted array would be generated in the first place. Any ideas?
Thank you for making this video! Could you please 'prove' that this would work for any general input?
yeah I could do a proof but not worth a full video ya know?
Hey ben, your approach fails for this example
4 3 1 2 5 with k=2
Any thoughts?
Liked your approach BTW
Isn't that '4' 3 positions away from it's final sorted position?
Thank you for your hard work on those videos. What do you think about doing an episode about dynamic programming? Explain top down and bottom up approaches, dp table method, how to approach it in general etc.
I could. I feel all the dp videos already teach this though. But I could make a video to tie it all together.
Thank you very much. I love the way you explain things.
sure
awesome explaination of underneath of the problem
thanks
I understand that its almost sorted and hence using the Heap Sort. Since it's no ,can't we try Counting sort? It will be O(n+k) faster than the approach?
I'm not sure
Next time can you make sure your biceps aren't blocking view of the board. Thanks.
For real though, this is an awesome explanation of the problem, and how to arrive at the solution. Most of these channels skip the thought process behind solving the question, and it's that type of critical thinking that will help people in their interview - not just memorizing algorithms. Thanks mate, keep up the good stuff!
Sure ha
This is such a great explanation. Thank you so much!!
Just a thought..Can we do it in using DEQUEUE instead of Min Heap..? we maintain the smallest element the queue for every k+1 window...
using DQUEUE it will be O(N)
I sort of know what you are saying.
Why a dequeue? Even if we maintain the smallest element, how are you cognizant of its position in the underlying structure for removal at all times?
Elaborate a little and analyze each operation, I'm interested.
@@BackToBackSWE I don't believe a sliding window will work here. This is because we need to always maintain the ordering of the elements to get the smallest value every time
Nice walk through. Love it!
sure
Hey man. Awesome video. probably the best placement-prep channel on youtube. like when you made that diagram, before you mentioned heap, heap popped into my mind and i paused the video and came up with the solution. initially when i saw the problem, i had no clue how this was going to happen.
Anyway I have a major doubt tho. Where can I learn the analysis of time and space complexities for all kinds of loops, recursion,divide conquer etc.
haha nice! That is so cool. And for time complexities... :) I'm making this twitter.com/thebigoguide, it'll be out the end of July. It's why I've been so quiet for so long on the channel
Silly question but what is the difference between this and the heap sort? Just the space complexity?
No question is silly, the only similarity is the data structure used to sort. If k=n then yes, this is basically heapsort where all items enter the heap and are placed out. But heapsort only uses the sift up subroutine in the initial build heap phase before the placement phase, and it only sifts up the first n/2 items one by one.
your videos are very helpful . thank you brother
sure
Awesome explanation.
thanks
thanks buddy, awsome explanation!!
I love your videos man!
thx
if k value is unknown is there a way to find k value faster than O(nlgn)
I was reviewing the code you put in the description. It makes sense for the most part, but why did you make it such that the min heap has k + 1 elements at any time instead of just k elements?
Because for the first position (and next positions onward) we compete k+1 elements. It is easiest if you look at the video and see concretely why.
@@BackToBackSWE I watched the video before the comment. I think I got it since I have had a night's sleep. I think it is because we include the first element plus the k elements to the right.
@@bob_jones yeah
Thankyou for such an amazing explanation...♥️
sure
Ben, great videos! I have been watching tons of your videos and it has helped me a lot! I have a quick question about this problem. Will bubble sort be a good strategy here? I feel like in this particular case bubble sort will have a time complexity of O(k*n) = O(n). Please correct me if I'm wrong.
thanks and how O(k*n)
@@BackToBackSWE In this case, to sort this array we would have to traverse it at most k times with bubble sort. I haven't actually worked it out so I may be wrong.
@@SupersonicProd Isn't bubble sort quadratic? I may be missing something
build a heap with k elements takes O(k) time so the time complexity is O(n*log(k) + k) == O(n*log(k))?
building a heap with k elements is log(k) per insertion (if we hold k items at max in heap) over k items so Θ(k*logk).
very nice explanation about the problem and solution (y)
thanks
Can please make videos mainly on backtracking, greedy, dynamic programming .. it will helpful ..because most people find those problem difficult to solve. Thanks
yeah
Perfect explanation!
thanks
We love u buddy! we love u! every buddy love you!
hey bro i'm here from your solutions on leetcode(minimum window susbstring):-
even though approach of your videos is good i think company wise questions approach would be better . for eg :- take all uber questions , then amazon etc . this covers the most asked ones and all the common interview questions irrespective of the company . hope i made sense .
cheers .!
Yes, this is something I pondered when I started this channel. How would I format things.
The thing is...I didn't think that that would be a good choice...to revolve a whole channel and movement around company specific questions....although it does align with the mission of the project (to get people jobs)...I just don't think it'd be a good idea to pander to the idea that companies ask a certain set of questions (although some DO do that) as a long-term content strategy.
It'd certainly get the channel WAY more views and give it a viral aspect but...
What if a company stops asking a question? What if they stop using these kinds of questions all together?
A more stable idea in my belief is to revolve the channel around classes of problem and the fundamentals that guide each problem class.
I think anyone can look up the company lists and then do those problems and then...yeah
I may just be straight wrong but eh...
Back To Back SWE i think your approach is the correct here. Fundamentals > any specific problem set Uber might have asked.
There is no guarantee that Amazon asks X, Google asks Y, etc. Interviewers at these companies are allowed to choose whatever question they want to ask, so it is possible (or even probable) that you could get a Facebook question at Google, a Palantir question at AirBNB, etc.
Hi ..In your code
for (int i = 0; i < k && i < n; i++) {
minHeap.add(arr[i]);
}
shouldn't this be ----- i < K+1 ?
I'm not sure, I wrote it a while back
Top class explanation
thanks
great explanation!!!!
thanks
LOL, I liked your final words, very casual :p
yoyo
This is actually the solution to a slightly different interview problem: k-left sorted array where elements cannot move left more than k positions. In you case the restriction is on both directions so it’s more complicated and your solution doesn’t work. Imagine the first element in your array is the biggest (10). It’ll stay in the min heap all the way to the end and will end up as the last one in the final array so it’d move more thank k=3 positions to the right
"Imagine the first element in your array is the biggest (10)".
In the video example the first element cannot 10. The only possible positions that 10 can end up if in a final sorted arrangement (as in the video example):
k = 3
arr = [ 6, 5, 3, 2, 8, 10, 9 ]
are
[ x, x, 10, x, x, x, x ] (3 to left)
[ x, x, x, 10, x, x, x ] (2 to left)
[ x, x, x, x, 10, x, x ] (1 to left)
[ x, x, x, x, x, 10, x ] (0 change)
[ x, x, x, x, x, x, 10 ] (1 to right)
"It’ll stay in the min heap all the way to the end and will end up as the last one in the final array so it’d move more thank k=3 positions to the right".
k cannot be 3 if the 10 is in first position (index 0).
What am I missing? I am confident that this is correct, but I may be wrong.
- Ben
Back To Back SWE I mean try the following input:
K = 3
Arr = [10, 6, 5, 3, 2, 8, 9]
10 shouldn’t move past 4th position
@@zdanodron Yes, that input is invalid is what I mean. 10 can't be there or else it breaks the problem description since it will be 6 positions from its "final resting place". Does that make sense?
It does not conform to the fundamental problem description that allows the approach to work in the first place.
The heap approach SHOULDN'T work for that input because of the very nature of it. It breaks our fundamental assumption about the possibilities at any one index. (the elimination we do in the video)
Back To Back SWE Fair enough. After reading the problem description again, I find you are correct indeed.
I’ve got confused because once I was asked a similar question to produce a K -sorted array for an arbitrary input
@@zdanodron No problem, it is no biggie. Glad I cleared it up, I got worried for a second 😅
Keep asking great questions, I'm happy you are challenging things. Continue. It is the sign of a great learner to challenge what they know and make these connections.
Really good videos.
thanks
There is a better way actually, build heap for first k+1 elements which takes O(k) time, and then do the operations for the remaining elements which would take O((n-k)(logk)), the total time complexity would be O(k+(n-k)logk) which is better than O(nlogk)
where is the code for it ?
The repository is deprecated - we only maintain backtobackswe.com now.
Really llove your explaination
thx
thumb up before watching
haha
this was good
thanks
where is the code?
The repository is deprecated - we only maintain backtobackswe.com now.
Totally awesome
Smart Idea, thank you (Y)
sure
بارک الله شعبون کد خدا بارک الله
Bro you been working out?
yeah, I've weakened though
super bro
thx
Thankyou Sir
sure
4:44 good stuff XD
With a small enough K probably worth just doing a straight linear minimum.
What is a straight linear minimum?
For anyone looking for a code implementation can look at the link below.
Hope this helps. I took this video as a reference for the code and also commented where it was required.
pastebin.com/2xRuGeAi
nice!
Thanks man :)
Wow
thx