Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note: You may assume k is always valid, 1 ≤ k ≤ n2.

Solution

public class Solution {
    public class Candid {
        int x;
        int y;
        public Candid(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int kthSmallest(int[][] matrix, int k) {
        if(matrix == null) return 0;
        int n = matrix.length;
        if(n == 0) return 0;

        int used[][] = new int[n][n];
        List<Candid> candid = new ArrayList<Candid>();
        candid.add(new Candid(0, 0));
        int cnt = 0;

        while(candid.size() != 0) {
            // find the candidate with the min value
            int min = Integer.MAX_VALUE;
            int minIdx = 0;
            int idx = 0;
            for(Candid can: candid) {
                if(matrix[can.x][can.y] < min) {
                    min = matrix[can.x][can.y];
                    minIdx = idx;
                }
                idx++;
            }

            // move the candidate
            Candid tar = candid.remove(minIdx);
            if(++cnt == k) return matrix[tar.x][tar.y];
            used[tar.x][tar.y] = 1;

            // check right and left
            checkCandid(used, candid, tar.x + 1, tar.y);
            checkCandid(used, candid, tar.x, tar.y + 1);
        }    
        return 0;
    }

    public void checkCandid(int[][] used, List<Candid> candid, int x, int y) {
        int n = used.length;
        if(x >= n || y >= n) return;
        if( (x == 0 || used[x - 1][y] == 1) && (y == 0 || used[x][y - 1] == 1) ) {
            candid.add(new Candid(x,y));
        }
    }
}