# 378. Kth Smallest Element in a Sorted Matrix

## Medium

***

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

**Example 2:**

<pre><code>Input: matrix = [[-5]], k = 1
<strong>Output:
</strong> -5
</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`

&#x20;

**Follow up:**

* Could you solve the problem with a constant memory (i.e., `O(1)` memory complexity)?
* Could you solve the problem in `O(n)` time complexity? The solution may be too advanced for an interview but you may find reading [this paper](http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf) fun.
