K Lists of Sorted Integers, Find Min Range - Google Interview Problem

[@patriksimurka]

The fact that this video doesn’t even have a thousand views is criminal! This is the first video ever I feel morally compelled to like, let alone comment on. Keep up the fantastic work, sir.

[@stablesort]

Glad you liked it! And thanks for the warm words =)

[@Sunny-ri4yo]

Your way of teaching is great sir!

[@stablesort]

Thank you for the compliment!

[@y.violetguo5305]

your animations explain the solution very intuitively. the videos are in general concise and to the point. please post more videos! thanks!

[@stablesort]

Thank you for leaving a few good words! I'll be putting more effort into making more videos soon =)

[@cacacharlie6820]

The visualization explained everything. How beautiful that you can see the concept and then write the code yourself. Please post some topological sort and graph questions

[@xiaozhizhu8465]

I think your video is really well prepared and answered all the questions that I have about this problem! Thank you so much!

[@stablesort]

Thanks for the compliment! I am glad to hear it.

[@aryanmaniyar7301]

Thanks :) A great way to visualize indeed!!

[@Ninja-nt6yt]

This channel is hands down the best resource I have found on youtube. The explanations are clear and visualization is fantastic. I think that StableSort can easily become the most popular algorithms channel on youtube, as most others do not focus on developing intuition like you, and all learners are hungry for that. Please keep making more such videos. Also, I would suggest to add more content as it would help us and attract millions of new subscribers.

[@stablesort]

Thanks for such warm words! Unfortunately I don't have enough time these days to keep producing videos frequently enough to reach such goals. I do plan on making more in the future, but this is just a hobby for me - nothing too ambitious =)

[@fantasy9960]

wow, I really love your real life example. This makes my understanding so much easier!!

[@Drcphd21341]

Great video, may I propose an alternative solution? We traverse each list seperately, and consider the case of the current element being the "middle" element of our solution. We then consider 2 scenarios: 1) our solution is [L, M, R ] where L and R are from List 1 and List 3 2) our solution is [ L , M ,R ] where L and R are from List 3 and List 1, respectively Finding the Ls and Rs can be done by simply binary searching on the 2 remaining lists for the element closest to M. The total time complexity would be O( (n1+n2+n3) *(logn1+logn2+logn3) ) but the space reduces to O(1)

[@stablesort]

That's an interesting idea. Thanks for sharing! Does this approach also work when K > 3? I suppose it could work, you just have to binary search each of the other lists for both bigger/smaller values, and register the min/max across all lists. Then if min/max found was better than previous min/max, save that off as a better solution, and then repeat. Cheers!

[@Drcphd21341]

@@stablesort Exactly, couldn't have said It better myself! As a side note, I really appreciate the quality of your videos, it's hard to find people who actually want to teach such topics with quality animations and not just plain code. I find it sad how the field is not "entertaining" enough for the masses, albeit its extremely challenging nature, so that the creators are incentivized to provide such quality content. Thanks for your efforts.

[@stablesort]

@@Drcphd21341 Thanks for the compliment! I do try to keep it a little bit on the "entertaining" side =)

[@windsonyang1441]

Another solution: 1. Sort all the elements from the different lists and also keep track of their index. For instance, [(2, 1), (4, 1), (5, 0), ..., (30, 2)] in the example. 2. Use two pointers to find the minimal range contain all the index.

[@stablesort]

That's a nice solution, thanks for sharing. I can see how that could work: the two pointers would establish a sliding window. You can then have a hashmap that keeps track of the number of items from each list that is currently in the sliding window. So if going from left to right, you keep moving the right pointer until there are K items in the hashmap. Then the left pointer could be moved if there is more than one item from the list that is referenced by the right pointer.

[@Sunny-qq6un]

Thank You very much, this have helped me.

[@stablesort]

Glad to hear it!

[@kakhatezelashvili3368]

Why do we always move up min pointer ? since range can also be decreased by moving max pointer back ?

[@stablesort]

Thanks for raising a question. The particular implementation described in the video uses a priority queue, which always dequeues the smallest value. As you pointed out, the problem could be solved in the reverse order - by going from right to left, always removing the largest value. Both approached are fine.

[@kakhatezelashvili3368]

@@stablesort Thanks for replying. So it appears that problem can be solved by moving either min or max pointer but not both of them at the same time :) Can I find mathematical proof of that ?

[@stablesort]

​@@kakhatezelashvili3368 Well, I don't claim to prove that it's not possible to move both left and right boundaries at the same time. I just claim that my solution to the problem runs in O(k log k) + O(n log k), which is pretty good =)

[@kakhatezelashvili3368]

@@stablesort Yes of course it's beautiful, I just wanted to prove that by moving only one of the pointers at a time (min or max) won't skip actual smallest range. I thought that shrinking our window can also be done by moving min and max inwards :) Just wondering that =)

[@RaoVenu]

At 3:33, you mentioned O(KlgK) to run. I am presuming that you are referring to initializing the priority queue. There is an optimization which can be performed to ensure that it is linear. stackoverflow.com/a/34697891 Anyway, thanks for the great video. Cheers

[@stablesort]

Thanks for the link - that was a good read. You are right - it'd be more optimal to first create a collection of all of the items that would go into the queue and initialize the queue with it. That should take O(k) instead of O(k log k), assuming Java's implementation of PriorityQueue uses the siftDown() algorithm. Cheers!

[@psychicgaming2377]

a request , use some dark background my eyes got scorched by the blue sky in this night.

[@stablesort]

OK, thanks for the suggestion. I'll experiment with a dark theme for the next video.