> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0378-kth-smallest-element-in-a-sorted-matrix.md).

# 0378. Kth Smallest Element in a Sorted Matrix

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

## Description

Given an `n x n` `matrix` where each of the rows and columns are 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.

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

## ac1: minHeap

similar to: <https://leetcode.com/problems/merge-k-sorted-lists/description/>

```java
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // edge cases
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0 || k <= 0) throw new IllegalArgumentException();


        // int[] node = new int[3];  // row, column, value
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {return a[2] - b[2];});
        for (int i = 0; i < matrix.length; i++) {
            pq.offer(new int[]{i, 0, matrix[i][0]});
        }

        // count
        int cnt = 0, res = 0;
        while (!pq.isEmpty()) {
            int[] h = pq.poll();
            cnt++;
            if (cnt == k) {
                res = h[2];
                break;
            } 
            h[1]++;  // move col pointer forward
            if (h[1] < matrix[h[0]].length) {  // if still in the range, put it back, otherwise discard it.
                h[2] = matrix[h[0]][h[1]];
                pq.offer(h);
            }
        }

        return res;
    }
}

// O(klogR) time, O(R) space
```

## ac2: binary search

even so hard to understand.

```java
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // edge cases
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0 || k <= 0) throw new IllegalArgumentException();

        int n = matrix.length;
        int l = matrix[0][0];
        int r = matrix[n-1][n-1];
        int count = 0;
        while (l < r) {
            int mid = l + (r - l) / 2;
            count = countLessEqual(matrix, mid);
            if (count >= k) r = mid;
            else l = mid + 1;
        }

        return l;

    }
    // return count of those less or equal to target
    private int countLessEqual(int[][] matrix, int t) {
        int n = matrix.length;
        int res = 0;

        for (int r = 0; r < n; r++) {
            int c = 0;
            while (c < n && matrix[r][c] <= t) c++;
            res += c;
        }

        return res;
    }
}

// O(nlog(max-min)) time, O(1) space
```

another version, template

```java
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // edge cases
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0 || k <= 0) throw new IllegalArgumentException();

        int n = matrix.length;
        int l = matrix[0][0];
        int r = matrix[n-1][n-1];
        int count = 0;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            count = countLess(matrix, mid);
            if (count >= k) r = mid;
            else l = mid;
        }
        // compair last left, right
        if (countLess(matrix, r) <= k-1) return r;
        else return l;

    }
    // return count of those less target
    private int countLess(int[][] matrix, int t) {
        int n = matrix.length;
        int res = 0;

        for (int r = 0; r < n; r++) {
            int c = 0;
            while (c < n && matrix[r][c] < t) c++;
            res += c;
        }

        return res;
    }
}
```