Kth smallest element in sorted matrix

O(k log(k)) solution.

• Build a minheap.

• Add (0,0) to the heap. While, we haven't found the kth smallest element, remove the top element (x,y) from heap and add next two elements [(x+1,y) and (x,y+1)] if they haven't been visited before.

We are doing O(k) operations on a heap of size O(k) and hence the complexity.

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, then you don't push anything). Both removing the minimum and adding a new element cost O(log n). At the jth step, you remove the jth smallest element, so after k steps you are done for a total cost of O(k log n) operations (where n is the number of rows in the matrix).

For the matrix above, you initially start with 1,2,7 in the heap. You remove 1 and add 3 (since the first row is 1 3 5) to get 2,3,7. You remove 2 and add 4 to get 3,4,7. Remove 3 and add 5 to get 4,5,7. Remove 4 and add 6 to get 5,6,7. Note that we are removing the elements in the globally sorted order. You can see that continuing this process will yield the kth smallest element after k iterations.

(If the matrix has more rows than columns, then operate on the columns instead to reduce the running time.)

This problem can be solved using binary search and optimised counting in a sorted Matrix. A binary search takes O(log(n)) time and for each search value it takes n iterations on average to find the numbers that are smaller than the searched number. The search space for binary search is limited to the minimum value in the Matrix at mat[0][0] and the maximum value mat[n-1][n-1].

For every number that is chosen from the binary search we need to count the numbers that are smaller than or equal to that particular number. And thus the smallest number can be found.

For better understanding you can refer to this video:

https://www.youtube.com/watch?v=G5wLN4UweAM&t=145s