My clean & clear Java Solution


  • 5
    A

    public class Solution {
    public int kthSmallest(int[][] matrix, int k) {

        PriorityQueue<Integer> pq= new PriorityQueue(k, Collections.reverseOrder());
        
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(pq.size()<k)
                    pq.add(matrix[i][j]);
                else{
                    int temp=pq.peek();
                    if(temp>matrix[i][j]){
                        pq.poll();
                        pq.offer(matrix[i][j]);
                    }
                }
            }
        }
        return pq.poll();
    }
    

    }


  • 0
    Z

    Clever solution and easy to understand!
    Thank you!


  • 0

    @alpit what is the meaning of it? I mean, it is the same as sort the whole array of matrix


  • 0
    L

    @alpit Sorry but this solution is not efficient. It essentially scans through the entire n^2 elements. The time complexity of this will be n^2 log k since you are using a max heap of size k. I don't know the best one but perhaps there are better ways to do it in nlogk or so.


Log in to reply
 

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