Last updated on January 9th, 2025 at 03:34 am

Here, we see a Kth Smallest Element in a Sorted Matrix LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Binary Search, Heap

Companies

Google

Level of Question

Medium

Kth Smallest Element in a Sorted Matrix LeetCode Solution

1. Problem Statement

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the k^th smallest element in the matrix.

Note that it is the k^th smallest element in the sorted order, not the k^th distinct element.

You must find a solution with a memory complexity better than O(n²).

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 8^th smallest number is 13

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

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is Modified Binary Search. This pattern is evident in the C++ and JavaScript implementations, where the solution uses binary search to narrow down the range of possible values for the k-th smallest element in the matrix. The Java and Python implementations, however, use a Sorting-based approach, which does not fall under the listed patterns.

3. Code Implementation in Different Languages

3.1 Kth Smallest Element in a Sorted Matrix C++

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n= matrix.size();        
        int l=matrix[0][0];
        int h = matrix[n-1][n-1];
        int mid;
        int count;
        while(l<h)
        {
            count=0;
            mid = l + (h-l)/2;
            for(int i=0;i<n;i++)
            {  
            count += upper_bound(matrix[i].begin() , matrix[i].end(),mid) - matrix[i].begin();
            }
                if(count<k)
            {
                l =mid+1;
            }
            else
            {
                h=mid;
            }
        }
        return l;
	}
};

3.2 Kth Smallest Element in a Sorted Matrix Java

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int [] arr = new int[n*n];
        int idx = 0;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                arr[idx++] = matrix[i][j];
            }
        }
        Arrays.sort(arr);
        return arr[k - 1];
    }
}

3.3 Kth Smallest Element in a Sorted Matrix JavaScript

var kthSmallest = function(matrix, k) {
    let lo = matrix[0][0], hi = matrix[matrix.length-1][matrix[0].length-1] + 1;
    while (lo < hi) {
        let mid = lo + Math.floor((hi-lo)/2);
        let count = 0;
        for (let i = 0;i<matrix.length;i++) {
            for (let j=0;j<matrix.length;j++) {
                if (matrix[i][j] <= mid) count++;
                else break;
            }
        }
        if (count < k) lo = mid+1;
        else hi = mid;
    }
    return lo
};

3.4 Kth Smallest Element in a Sorted Matrix Python

class Solution(object):
    def kthSmallest(self, matrix, k):
        temp = []
        for row in matrix:
            temp.extend(row)
        temp.sort()
        return temp[k-1]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n * log(max-min) + n * log(n))	O(1)
Java	O(n² * log(n²))	O(n²)
JavaScript	O(n² * log(max-min))	O(1)
Python	O(n² * log(n²))	O(n²)