# [LeetCode 378. Kth Smallest Element in a Sorted Matrix](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/608/week-1-july-1st-july-7th/3805/)
### Daily challenge Jul 7, 2021 (MEDIAN)

>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 **k^th^** smallest element `in the sorted order`, **not** the **k^th^ distinct** element.

:::info
**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 8^th^ smallest number is 13
:::

:::info
**Example 1:**
**Input:** matrix = [[-5]], k = 1
**Output:** -5
:::

:::warning
**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
:::

---

### Approach 1 : Brute Force :bulb:
**`72 ms`**

將所有元素放入 vector 中並**排序**，最後回傳 **`vector[k-1]`**.

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {     
        vector<int> list;
        
        for(int i=0; i<matrix.size(); i++){
            for(int j=0; j<matrix[i].size(); j++){
                list.push_back(matrix[i][j]);
            }
        }
        sort(list.begin(), list.end());
        
        return list[k-1];
    }
};

### Approach 2 : Heap ( Priority Queue ) :book:
**`24 ms`** **`O(min(K,N) + K*logN)`**

遍歷所有元素並存入 **`maxHeap`**。

當 `maxHeap`的大小等於 *`k`* 時，判斷當前元素 **`matrix[i][j]`** 是否小於 top of maxHeap。
>小於 ---> **`pop maxHeap`** and **`push matrix[i][j]`**
>大於 ---> **`break the loop`**， because *matrix* is sorted in non-decreasing order, the elements after `matrix[i][j:]` are bigger than current one and won't be the answer.

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        priority_queue<int> pq;
        
        int size = matrix.size();
        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                if(pq.size() < k)   pq.push(matrix[i][j]);
                else{
                    if(matrix[i][j] > pq.top()) break;
                    else    pq.pop(), pq.push(matrix[i][j]);
                }
            }
        }
        
        return pq.top();
    }
};

### Approach 3 : Binary Search :book:
**`28 ms`** **`O(M*N + logD)`** where *D <= 2 * 10^9^* is the difference between maximum and minimum elements in the matrix.
:::info
[Detail Explaination :book:](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/608/week-1-july-1st-july-7th/3805/discuss/1322101/C++JavaPython-MaxHeap-MinHeap-Binary-Search-Picture-Explain-Clean-and-Concise)
:::

:::success
使用 Binary Search 尋找當 `middle = #` 時，有多少元素小於等於 `middle`，盡可能找到最小的答案。
:::

We are trying to find the answer as small as possible ( use **`ans`** to store ) :

>Initial state :
n = matrix.size() ; m = matrix[0].size.
left = matrix[0][0] ; right = matrix[n-1][m-1]
middle = left + (right - left) / 2

How to count the number of elements in matrix that is less or equal to middle?
> **`row`** starting from **`0`** ; **`col`** starting from **`m-1`** in every **`row`** ; **`count = 0`**.
>* If **`matrix[row][col] <= middle`**, we can know that there are **`col + 1`** elements less or equal to middle.
>* If **`matrix[row][col] > middle`**, decreasing **`col`** until **`matrix[row][col] <= middle`**.
>* After we traversing all the ROWs :
>>1. If **`count >= k`** ---> **`right = middle - 1`** ( find smaller answer), and store current **`ans = middle`**.
>>2. If **`count < k`** ---> **`left = middle + 1`**.


class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        // binary search
        int n = matrix.size(), m = matrix[0].size();
        int left = matrix[0][0], right = matrix[n-1][m-1];
        int ans;
        
        while(left <= right){
            int middle = left + (right - left) / 2;
            int count = 0;
            for(int i=0; i<n; i++){
                int j = m - 1;
                while(j >= 0 && matrix[i][j] > middle)    j--;  
                count += j + 1;
            }
            
            if(count >= k){
                ans = middle;
                right = middle - 1;
            }
            else    left = middle + 1;
        }
        
        return ans;
    }
};