Kth Smallest Element in a Sorted Matrix LeetCode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Facebook Google Microsoft Twitter UberViews 1584

Problem Statement

Kth Smallest Element in a Sorted Matrix LeetCode Solution – We are given a matrix of size n where each of the rows and columns is sorted in ascending order. We are asked to return the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element and memory complexity must be better than O(n^2).

Examples & Explanations

Example 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13

Example 2:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 6
Output: 12
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 6th smallest number is 12

Example 3:

Input: matrix = [[-5]], k = 1
Output: -5

Approach

Let’s try to solve this problem without considering any space complexity constraint. We can use an array to store all the numbers in the matrix. This will take O(n^2) time, then we can simply sort the array & return the kth element. This will take O(logN) time. Since this array will take all the elements in the matrix and the matrix contains n x n elements. Therefore, the space complexity will be O(n^2).

Can we do better?

We will use priority queue “pq” to store all the elements of the matrix, whenever the size of pq becomes more than k, we delete the maximum element and insert the next element. Since we are using a priority queue, it will keep itself sorted in descending order.

Code

C++ code for Kth Smallest Element in a Sorted Matrix

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        priority_queue<int, vector<int>> pq, t;
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                pq.push(matrix[i][j]);
                if(pq.size()>k) 
                    pq.pop();
            }
        }
        // t=pq;
        // while(!t.empty()) {
        //     cout<<t.top()<<" ";
        //     t.pop();
        // }
        return pq.top();
    }
};

Java code for Kth Smallest Element in a Sorted Matrix

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1));

        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                pq.offer(matrix[i][j]);
                if(pq.size() > k)
                    pq.poll();
            }
        }
        return pq.poll();
    }
}

Complexity Analysis for Kth Smallest Element in a Sorted Matrix LeetCode Solution:

  • Time: O(M*N*logK) where M ≤ 300 is the number of rows, N ≤ 300 is the number of columns.
  • Space: O(K), space for heap which stores up to k elements
Translate »