Share my Java solution,could anyone tell me what's the complexity of my code?

  • 0

    Since the matrix is sorted, the smallest element should be matrix[0][0]. The next possible smallest element should be the right or the down element. Then I put these two elements in a PriorityQueue. Therefore we can always track the next smallest element, until we have the k-th element.

    Can anyone tell me what's the complexity of my code??
    The runtime is 38ms, can it be better??


    public class Solution {
        private class Pair{
            int x;
            int y;
            int val;
            public Pair(int x, int y, int val){
                this.x = x;
                this.y = y;
                this.val = val;
        public int kthSmallest(int[][] matrix, int k) {
            if(matrix.length ==0 || matrix[0].length ==0){
                return 0;
            PriorityQueue<Pair> pq = new PriorityQueue<Pair>(k, new Comparator<Pair>(){
                public int compare(Pair p1, Pair p2){
                    return, p2.val);
            boolean[][] visited = new boolean[matrix.length][matrix[0].length];
            for(int i =0; i< visited.length; i++){
                Arrays.fill(visited[i], false);
            Pair p = new Pair(0,0, matrix[0][0]);
            visited[0][0] = true;
            int result = 0;
            while(k !=0 && !pq.isEmpty() ){
                Pair top = pq.poll();
                result = top.val;
                if(top.x+1 < matrix.length && !visited[top.x+1][top.y]){
                    Pair right = new Pair(top.x+1, top.y, matrix[top.x+1][top.y]);
                    visited[top.x+1][top.y] = true;
                if(top.y+1 < matrix[0].length && !visited[top.x][top.y+1]){
                    Pair down = new Pair(top.x, top.y+1, matrix[top.x][top.y+1]);
                    visited[top.x][top.y+1] = true;
            return result;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.