> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/binary-search/bs-over-answer-space-answer-space/378.-kth-smallest-element-in-a-sorted-matrix.md).

# 378. Kth Smallest Element in a Sorted Matrix

## Problem Statement

<br>

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)`.

&#x20;

**Example 1:**

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

**Example 2:**

<pre><code><strong>Input: matrix = [[-5]], k = 1
</strong><strong>Output: -5
</strong></code></pre>

&#x20;

**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`

## Intuition

```
We use Upperbound as sorted to find min no of elements before 
For every mid
```

### Links

<https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/>

### Video Links

<https://www.youtube.com/watch?v=MOe7LlagCN8&ab_channel=AryanMittal>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
	int count_smaller(vector<vector<int>>& arr, int mid){
		int count = 0;
		for(int i=0; i<arr.size(); i++){
			count += upper_bound(arr[i].begin(), arr[i].end(), mid) - arr[i].begin();
		}

		return count;
	}

    int kthSmallest(vector<vector<int>>& arr, int k) {
		int m = arr.size(), n = arr[0].size();
		int low = arr[0][0], high = arr[m-1][n-1];
		int ans;
    
		while(low <= high){
			int mid = low + (high - low)/2;
			int ct = count_smaller(arr, mid);

			if(ct >= k){
				high = mid - 1;
				ans = mid;
			}
			else{
				low = mid + 1;
			}
		}

		return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###