Last updated on July 20th, 2024 at 04:09 am

Here, We see Kth Smallest Element in a Sorted Matrix LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Binary Search, Heap

Companies

Google

Level of Question

Medium

Kth Smallest Element in a Sorted Matrix LeetCode Solution

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

1. Kth Smallest Element in a Sorted Matrix LeetCode Solution 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;
	}
};

2. Kth Smallest Element in a Sorted Matrix Solution 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. Kth Smallest Element in a Sorted Matrix Solution 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
};

4. Kth Smallest Element in a Sorted Matrix Solution Python

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