klogk Java solution


  • 0
    L

    It is similar to the question where you could merge from multiple sorted arrays using a min heap. Here is the sample code:

        public int kthSmallest(int[][] matrix, int k) {
         if(matrix==null || matrix.length==0 || k>matrix.length*matrix[0].length) {
             return 0;
         }   
         //Read row-by-row till we get to kth smallest.
         PriorityQueue<Wrapper> queue = new PriorityQueue<>();
         for(int i=0;i<matrix[0].length;i++) {
             queue.add(new Wrapper(0,i,matrix[0][i]));
         }
         int count=0;
         while(count<k) {
             Wrapper obj = queue.poll();    
             count++;
             if(count==k) {
                 return obj.val;
             }
             if(obj.i<matrix.length-1) {
                queue.add(new Wrapper(obj.i+1,obj.j,matrix[obj.i+1][obj.j]));
             }
             
             
         }
         return matrix[0][0];
        }
        private class Wrapper implements Comparable<Wrapper>{
            int i;
            int j;
            int val;
            Wrapper(int i,int j, int val) {
                this.i = i;
                this.j = j;
                this.val = val;
            }
            public int compareTo(Wrapper o) {
                return this.val-o.val;
            }
        }
    

Log in to reply
 

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