Kth Smallest Number in Sorted Matrix

Find the kth smallest number in at row and column sorted matrix.

Given k = 4 and a matrix: [ [1 ,5 ,7], [3 ,7 ,8], [4 ,8 ,9], ] return 5

O(k log n), n is the maximal number in width and height.

KeyPoints

1. BruteFore/Merge Sort takes O(mnlg(mn)) which contains a lot of unnecessary operations, since they not only sort the 0-k part but also k-m*n part.
2. Use heap to gradually increase the searching coverage, in another word, minimize the coverage. For Kth smallest Number, just call heap.poll() k-1 times then peek() to get the result.

Method 1: O(3nlgn) O(2n)

1. Build a min stack
2. Poll the minimum value and increase the coverage based on that, in this case, it's the left and below of the minimum element.
3. Use HashSet to prevent duplicate offer() to the heap.

Method 2: O(2nlgn) O(n)

1. Build a min stack
2. Offer() the whole line/column to the heap
3. Same as Method 1 but only increase the coverage by one direction, eg. if the whole line is already in the heap, then each time the minimum is polled, just put the left element of the minimum.
4. Somehow similar to the navie way to merge N sorted array.