O(klogn) solution using Priority Queue


  • 0
    public int kthSmallest(int[][] matrix, int k) {
            PriorityQueue<int[]> smallestTracker = new PriorityQueue<int[]>(new Comparator<int[]>(){
                public int compare(int[] a, int[] b) {
                    Integer x = matrix[a[0]][a[1]];
                    Integer y = matrix[b[0]][b[1]];
                    return x.compareTo(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 of this solution is O(kLogn) and the space complexity is O(n)


Log in to reply
 

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