SHORTEST RANGE IN K SORTED LISTS - CODING INTERVIEW QUESTION AT GOOGLE, APPLE OR FACEBOOK

[@SuccessinTech]

NEW: Check out my brand new website www.successintech.com

[@pagrus7]

I think space complexity of the naive solution is O(k), since it requires maintaining k pointers/indicies along the way.

[@jasonzhang2643]

I agree with this.

[@tianwenchu1663]

Agree with O(K)

[@dgmneto]

I agree with Pavel

[@JamshadAhmad]

Yup, number of pointers will increase with number of lists.

[@aliparsaei]

Interesting question. I'd like to note that the worst-case-scenario time complexity of the "naive" & optimized solutions are O(k^2 * n) & O(k * log(k) * n) respectively.

[@hanyu4758]

Space Complexity should be O(k), for each array you need to keep the index of element of this array when searching the range.

[@praveengupta5693]

I think the time complexity for naive approach is O(n*k*k) and for min heap it would be O(n*k*logk) where n is the number of elements in a single array and k is the number of list.

[@jasonzhang2643]

I agree. But I think when he said n, he is referring to the # of numbers of elements in all the lists

[@AlissonSiri]

Why do you think that? He would loop through n elements k times, that's O(n*k). Can you explain your thoughts?

[@federicomengozzi4785]

Alisson Siri loop trough all elements in O(n*k) and find the new minimum with k operation hence O(n*k*k). Whereas with the heap, while iterating over all elements in O(n*k), you could find the minimum in log(k) for a total running time of O(n*k*lg(k))

[@Embarassedmess5634]

Nice video!!. Its a hard problem in Leetcode. Explanation makes it very simple. Thank you!

[@AnonyoX]

The space complexity could be O(k) for the k pointers. The only way it could be constant is if (1) the list is a linked-list, not array, and (2) we are using the 'head' node's pointer itself for traversing (and effectively truncating the list(s) as we go). The head node doesn't count as separate space, as it is in the input.

[@himanshutanwar1774]

Space complexity should be O(k). Because you would be storing the k iterators. Am I right?

[@kentnguyen2182]

Wow did he just said we always increase the min pointer, but he didn't explain why?! that's important

[@adityaekawade1060]

Kent Nguyen The lists are sorted, and we want to find minimize the value of range. So when we move to the next element, we increase the chance to minimize the value of range. For example our list is [0 , 1, 2 , 3] And for first index which is the min value, we get the range value as 5. So when we move to the next index which has the value 1, our range would be 4, and so on..

[@SuccessinTech]

What are you hinting at? It's a linear search through the list.

[@pagrus7]

I guess he is hinting at the lack of explanation of why the algorithm is correct; how do we know it will work on other inputs. For me it was helpful to imagine k lists, the desired answer as a set of indicies, and then persuading myself that: - the algorithm will encounter the desired "min" before it encounters the desired "max" (or at the same time, in a special case) - once it encounters the "min" of a minimal range, the pointer for that list won't move until the algorithm sees the "max" of the range. - the "min" pointer also won't move away until every other element is in the [min, max] range ... which means that during the execution the algorithm is ought to see the intended answer.

[@SuccessinTech]

+Pavel Grushetzky Very well explained!

[@eeyore345]

@@pagrus7 Thanks for explaining, I was wondering why moving the min forward too.

[@anshubansal2008]

Great simple solution for the complex question. Thanks for the video

[@cristianouzumaki2455]

Haven't seen a hard level prob explained so simply.

[@srikid100]

In addition to Min heap , don't we need a Max heap as well as we need to keep track of the maximum element as well to calculate the range ? Please comment

[@SuccessinTech]

+srikid100 No you keep track of the „local“ max (thats how it‘s often called in literature) with k variables, whose value you override whenever the algorithm finds a new max.

[@rishidaryanani1333]

Success in Tech could you please explain this a little more? From the local min, local max and the min range - all of which require us to look at k elements in the current solution - what exactly goes into the min heap? If we still need to find the local max by going through k values then isn’t the time cost O(k)?

[@soumyasengupta7018]

Rishi Daryanani we dont go through all the elements to track the local max. 1> first elements from all the lists are initially added to the min heap..while adding we keep track of local min & local max while adding them to heap. 2> when you pop the minimum element from heap and add new elem from same list, there are 2 scenarios. New elem is bigger than rest elems in heap,u compare it with the previously calculated local max and update accordingly. Then you perform heapify again which gives you the min element to be removed again..so up update min variable again and this process goes on until and unless u reach the end of a list. So at a time you process k elements where each element is from a different list. Space complexity is k for heap. Time complexity for intial heapsort of k elements is k_log k. When you remove min from heap and add new element the time complexity of heapify is log k. The above process is repeated at max (nk-k)log k times. So total complexity is (nk-k) log k + k log k = nklogk. Hope this helps you. Happy coding.

[@girikgarg1268]

@@soumyasengupta7018 But how do you "keep track of local min & local max while adding them to heap."?

[@girikgarg1268]

It would be better if you could explain it through code

[@rootchutney6567]

Just curious.. what would be the change be in case of duplicates across lists ? Will a recursive step of increasing multiple min pointers(one by one) be sufficient or is there a better solution out there ?

[@7daniel49]

Bah, I just spent 5 mins typing out why which duplicate min you move matters, but it doesn't. If you just move the min each time, you will cover all necessary ranges. If there are multiple, just move one of the mins, then the next loop will move the next one and so on.

[@hrithiktg4054]

use 3 max-heaps....first..to build a maxheap, it takes O(n) time, n being the length of the list.....later iteratively compare the root of the heaps...find min and max....it takes O(k) time for this....find the range....next, pop the the element from the max-heap whose root was found to be maximum(in other words the heap which has root the greatest).......continue....you'll get it! total time : O(klog(n)) space : O(1)

[@manbendrasingh2481]

Your algorithm would work but I don't agree with the time complexity you mentioned for your approach. You would end up removing n elements from the heap so you will spend n time also at every step you would also do heapify which would add extra log(n) at every step. So the time complexity for your algorithm would be O(k*n*log(n))

[@hrithiktg4054]

No, "k" lists are already given to you(in this case k=3). You just need to heapify those lists, to get max heap.Heapify takes O(n) time.where "n" is the number of elements in corresponding lists.to find the min, it takes O(k) time.

[@hrithiktg4054]

but yeah, i need to remove the max elements, i takes O(logn) time.so the total complexity is O((k+logn)*N). where, "N" is the sum of the length of the individual list.and "n", lenght of a sigke list.the above complexity is accurate if all the input lists are of length "n".

[@rajasubasubramanian9365]

Just loved it !! Thanks for the video @Ramon Lopez :)

[@legendleft]

nice video man! i'll be coming back to your channel

[@Dominatoification]

good stuff

[@edithau8919]

In your approach, you need to do the min-comparison 4*4*4 times (4-0-5, 4-0-18, 4-0-22, 4-0-30, 10-0-5, 10-0-18....), and hence O(n^k). The time complexity O(n * k) does not seem possible to me. Could you please provide psuedocode for the time complexity O(n * k)?

[@federicomengozzi4785]

Edith Au actually if you consider n to be the number of elements in each list. The running time for the naive algorithm would be O(n*k*k) because while loop through all elements you would need to find the minim in O(k). In the video he was probably considering n as the number of all elements (n ＝ sum[i in 0..k] #elemList(i))

[@nitinagrawal6637]

I am not an expert, but saying this approach is Naive may not be correct. Keeping the solutions simples & easy to understand is not a naive approach but can be rather efficient approach in most cases. As coining the terms of other DS like MinHeap, one can boast about his knowledge but it can be dangerous. As if we use MinHeap, then it also takes its own space & time to maintain that structure & here I think, we just need the min at each step & I dont know what significant improvement one can get after using MinHeap here.

[@almazglaz]

isn't it O(n*k*k)? as we also need to move each of k pointers n times and k for searching max/min(which can be optimized to log k)

[@dgmneto]

almazglaz yes, I believe you are correct. At least, that's what I understood from the solution.

[@buttofthejoke]

Moving each pointer is a single instruction. When calculating Big O, we ignore such instructions and only calculate number of iterations.

[@rumenstoyanov1701]

Yes you are correct, it is one operation for every array entry access which is nk and then a linear search O(k) to find the min/max, hence nk^2

[@quantlfc]

Thanks! :)

[@gsniteesh3794]

Try adding a link to the code for each and every problem you solve

[@kratijain]

If 30 in 3rd list is replaced by 23, will the algorithm still be unable to find the minRange??

[@prateeksinghal7114]

Just a heads up to guys understanding the time complexity. Here n is the total number of elements in all the k lists.

[@abhitrades6061]

the code you explained takes O(n*k*k)

[@veerrajuyeleti8541]

sir pls add videous on dynamic programming

[@dhiresh5980]

This video felt like going through the algorithm but not explaining it

[@swanhtet1]

Exactly!

[@dmitry926]

O(n * log k) doesn't look correct and it wasn't explained in the video.

[@ADITYAKUMAR-yd3ow]

I think time complexity should be O(max(length's of lists) * K). Isn't it?

[@jllapin]

Isn't it faster and easier to code to traverse the first array and then move the iterator in every other array to the one that is closest to the current element in the first array? static int[] GetMinRange(List lists) { int[] retVal = null; int[] indexes = new int[lists.Count]; for (int x = 0; x < lists[0].Count; x++) { indexes[0] = x; for (int y = 1; y < lists.Count; y++) { while(indexes[y] < lists[y].Count - 1) { if (lists[0][x] - lists[y][indexes[y]] > lists[0][x] - lists[y][indexes[y] + 1]) { indexes[y]++; } else break; } } retVal = GetMin(lists, indexes, retVal); } return retVal; } static int[] GetMin(List lists, int[] indexes, int [] retVal) { int max = lists[0][indexes[0]]; int min = lists[0][indexes[0]]; for (int x = 0; x < indexes.Length; x++) { if (lists[x][indexes[x]] < min) min = lists[x][indexes[x]]; else if (lists[x][indexes[x]] > max) max = lists[x][indexes[x]]; } if (retVal == null || retVal[1] - retVal[0] > max - min) return new int[] { min, max }; return retVal; }

[@PoulJulle-wb9iu]

How to disguise the Danish accent lol

[@SuccessinTech]

Austrian ;)

[@shoooozzzz]

You have to assume there are no duplicates, otherwise this approach will not work. It is impossible to know which x,y,z pointer to increment when there is a tie in the lowest value.

[@xiangyuzhao6363]

As far as I see, there won't be a problem if duplicates exist. You can increase either one when there is a tie. Please correct me if I'm wrong, an example would be great.

[@7daniel49]

​@@xiangyuzhao6363 @Ben Wright I was convinced duplicates changed the code, I wrote my solution to address that, but it doesn't. ex. [[14, 17, 21], [14, 34, 35], [20, 21, 24]] - if we prioritize the first list our x, y, z are: 14, 14, 20 -> 17, 14, 20 -> 17, 34, 20 (we have moved from 14s and range is 6) - if we prioritize the second list the x, y, z are: 14, 14, 20 -> 14, 34, 20 -> 17, 34, 20 (moved from 14s, again range is 6) We still look at all the cases, just in a different order.