# Kth Smallest Element In A Sorted Matrix Problem

## Description

LeetCode Problem 378.

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^2).

Example 1:

``````1
2
3
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:

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

Constraints:

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

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();

int left = matrix, right = matrix[n-1][n-1];
int mid;

while (left < right) {
mid = (left + right) / 2;
int lessthanmid = 0;
int i = n-1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] <= mid) {
j ++;
lessthanmid += i+1;
} else {
i --;
}
}
if (lessthanmid < k) {
left = mid + 1;
} else {
right = mid;
}

}
return left;

}
};
``````