arrays - Kth smallest element in sorted matrix - Stack Overflow

False. Consider a simple matrix like this one: 1 3 5 2 4 6 7 8 9 9 is the largest (9th smallest) element. But 9 is at A[3, 3], and 3+3 != 9. (No matter what indexing convention you use, it cannot be true). You can solve this problem in O(k log n) time by merging the rows incrementally, augmented with a heap to efficiently find the minimum element. Basically, you put the elements of the first column into a heap and track the row they came from. At each step, you remove the minimum element from the heap and push the next element from the row it came from (if you reach the end of the row,

Read full article from arrays - Kth smallest element in sorted matrix - Stack Overflow