Google | Phone | K Smallest in Sorted Array
Anonymous User
801

Question 1 - LC - 378. Kth Smallest Element in a Sorted Matrix
Question 2 - Follow-up on above: Instead of finding only the kth smallest, output the first k smallest in this row and column sorted array.

Was able to only provide a O(klogn) solution, which in worst case (k is close to n^2) this is the samse time complexity as the naive sorting solution. Not sure if there is any better solution (feels to me there should be one because the O(klogn) solution does not use the column is sorted part).

Comments (3)