# 378. Kth Smallest Element in a Sorted Matrix

### Leetcode

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

### 題目

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.

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

矩陣的列會往右遞增、欄會往下遞增，故左上角一定是最小的數字，右下角一定是最大的數字。根據以上條件，我們可以把最小值設成左上的值、最大值為右下的值，進行 binary search，最初拿 mid 值去跟矩陣**左下角**的數字比較，逐步求得矩陣有多少個數(cnt)其數值是小於 mid 的 (如果 mid > 左下角值代表 mid 也大於這整欄所有的數值，所以 cnt += row 的列數，再依序往右、往上尋找，最終找出多少個數字是小於 mid 的)，如果 cnt 小於 k，代表我們的 mid 值太小，所以要往數值大的方向尋找 (mid+1 \~ end)，最終當 start 與 end 值相同的時候，就是我們要找的數字了。

```
var kthSmallest = function(matrix, k) {
  const n = matrix.length;

  function getCntLowerThen(value) {
    let cnt = 0;
    let row = n - 1;
    let col = 0;

    while (row >= 0 && col < n) {
      if (matrix[row][col] <= value) {
        cnt += row + 1;
        col++;
      } else {
        row--;
      }
    }
    return cnt;
  }

  let start = matrix[0][0];
  let end = matrix[n - 1][n - 1];
  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    const cnt = getCntLowerThen(mid);

    if (cnt < k) {
      start = mid + 1;
    } else {
      end = mid;
    }
  }

  return start;
}
```

Runtime: 60 ms, faster than 99.65% of JavaScript online submissions for Kth Smallest Element in a Sorted Matrix. **O(n\*lg(max-min))**

Memory Usage: 41.3 MB, less than 98.96% of JavaScript online submissions for Kth Smallest Element in a Sorted Matrix.

<https://anj910.medium.com/leetcode-378-kth-smallest-element-in-a-sorted-matrix-%E4%B8%AD%E6%96%87-318d52f366af>

### 測資

```
let matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8;

console.log(kthSmallest(matrix, k));
```

### 參考資料

1. <https://anj910.medium.com/leetcode-378-kth-smallest-element-in-a-sorted-matrix-%E4%B8%AD%E6%96%87-318d52f366af>
