Leetcode: Kth smallest element in matrix
n*n matrix, find the
kth smallest element. Each row in the matrix is sorted in ascending order and independent of the other rows. Do not use
O(n*n) space when solving this. One example matrix looks like this:
If we could use all the space we wanted, we could just perform an n-way merge sort on every row at once. This would work because the rows itself are sorted already. Afterwards, we would need to pick the kth element from the list and would be done.
The solution I came up with uses
O(n) space. That is one space for a pointer to each row and column. Initially we set all rows to the first column. Then we iterate over all rows and find the smallest element in this particular position. We advance the pointer to this element by 1. Afterwards we check if we left the bounds of this array. If we did, we remove the row as a possible candidate. Finally, we take the remaining pointers and write them in a list which we sort. From that sorted list, we pick the smallest value and return it.
Runtime: 4712 ms, faster than 5.02% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix. Memory Usage: 18.6 MB, less than 80.92% of Python3 online submissions for Kth Smallest Element in a Sorted Matrix.