Algorithm

Problem Name: 378. Kth Smallest Element in a Sorted Matrix

Given an `n x n` `matrix` where each of the rows and columns is sorted in ascending order, 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.

You must find a solution with a memory complexity better than `O(n2)`.

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 = [[-5]], k = 1
Output: -5
```

Constraints:

• `n == matrix.length == matrix[i].length`
• `1 <= n <= 300`
• `-109 <= matrix[i][j] <= 109`
• All the rows and columns of `matrix` are guaranteed to be sorted in non-decreasing order.
• `1 <= k <= n2`

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
int kthSmallest(int** matrix, int matrixRowSize, int matrixColSize, int k) {
int kth;
int i, j, l, r, c, *last_row;

last_row = malloc(matrixColSize * sizeof(int));
//assert(last_row);
memset(last_row, -1, matrixColSize * sizeof(int));

r = c = 0;
kth = matrix[r][c];
last_row[c] = r;

while (-- k) {
r = matrixRowSize - 1; c = matrixColSize - 1;
kth = matrix[r][c];  // the biggest value
l = 0;  // line was previous tested
i = 1;  // line to be tested
for (j = 0; j  <  matrixColSize && i != 0; j ++) {
// for every column, look at the next row of the one was already taken
i = last_row[j] + 1;
if (i  <  matrixRowSize && i != l && kth > matrix[i][j]) {
kth = matrix[i][j];
r = i; c = j;
}
l = i;
}
last_row[c] = r;  // mark this one being taken
}

free(last_row);

return kth;
}
``````
Copy The Code &

Input

cmd
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
priority_queue < int, vector<int>, greater < int>>pq;
for(auto x: matrix)
for(auto y: x) pq.push(y);
while(--k) pq.pop();
return pq.top();
}
};
``````
Copy The Code &

Input

cmd
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

Output

cmd
13

#3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int numOfRows = matrix.length;
PriorityQueue < int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
for (int j = 0; j  <  numOfRows; j++) {
}
for (int i = 0; i  <  k - 1; i++) {
int[] removed = pq.poll();
if (removed[0] == numOfRows - 1) {
continue;
}
pq.add(new int[]{removed[0] + 1, removed[1], matrix[removed[0] + 1][removed[1]]});
}
return pq.peek()[2];
}
}
``````
Copy The Code &

Input

cmd
matrix = [[-5]], k = 1

Output

cmd
-5

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
/**
* @param {number[][]} matrix
* @param {number} k
* @return {number}
*/
const kthSmallest = function(matrix, k) {
let lo = matrix[0][0],
hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1; //[lo, hi)
while (lo  <  hi) {
let mid = Math.floor(lo + (hi - lo) / 2);
let count = 0,
j = matrix[0].length - 1;
for (let i = 0; i  <  matrix.length; i++) {
while (j >= 0 && matrix[i][j] > mid) j--;
count += j + 1;
}
if (count  <  k) lo = mid + 1;
else hi = mid;
}
return lo;
};

console.log(kthSmallest([[-5]], 1));
console.log(kthSmallest([[1, 2], [1, 3]], 4));
console.log(kthSmallest([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 8));
console.log(kthSmallest([[1, 2], [1, 3]], 2));
``````
Copy The Code &

Input

cmd
matrix = [[-5]], k = 1

Output

cmd
-5

#5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def kthSmallest(self, matrix, k):
return sorted(itertools.chain(*matrix))[k - 1]
``````
Copy The Code &

Input

cmd
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

Output

cmd
13