Kth Smallest Number in n x n Matrix

$\mathtt{REFERENCE}$ @ LeetCode

$\mathtt{RELATED\ PROBLEM\ -\ K\ Smallest\ Sum\ Pair}$

Task Description

Given an $n \times n$ integer Matrix sorted in non-decreasing order in row and column wise.

Find $kth$ smallest number in the matrix.

Solution 1 : Brute Force Solution

The naive solution would be to traverse through all the elements, sort them and find the $kth$ smallest item. There are $n^2$ elements in the matrix. Sorting them will take ${\cal O}(n^2log(n^2))$ time.

Solution 2: Efficient Solution

This Brute Force solution can be optimized by using Priority Queue. This solution is similar to the problem K Smallest Sum Pair.

    /**
    * Computes the Kth smallest item in the given row and column wise sorted 2D Matrix
    *
    */
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<int[]> smallestTracker = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                int x = matrix[a[0]][a[1]];
                int y = matrix[b[0]][b[1]];
                return x - y;
            }
        });
        
        for(int i = 0; i < matrix.length; i++) {
            smallestTracker.add(new int[]{i, 0});
        }
        
        int count = 0;
        int[] smallest = null;
        while (count < k) {
            smallest = smallestTracker.remove();
            if (smallest[1] < matrix.length - 1) {
                smallestTracker.add(new int[]{smallest[0], smallest[1] + 1});
            }
            count++;
        }
        return matrix[smallest[0]][smallest[1]];
    }

    

Time Complexity

Overall Time complexity is ${\cal O}(k log(n))$. The value $k$ can be $n^2$.
The space complexity is ${\cal O}(n)$ for the size of priority queue.

---

---

---