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??

    Thanks.

    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>(){
                @Override
                public int compare(Pair p1, Pair p2){
                    return Integer.compare(p1.val, 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]);
            pq.add(p);
            visited[0][0] = true;
            
            int result = 0;
            while(k !=0 && !pq.isEmpty() ){
                Pair top = pq.poll();
                result = top.val;
                k--;
                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]);
                    pq.add(right);
                    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]);
                    pq.add(down);
                    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.