<p>Given an <code>n x n</code> <code>matrix</code> where each of the rows and columns is sorted in ascending order, return <em>the</em> <code>k<sup>th</sup></code> <em>smallest element in the matrix</em>.</p>

<p>Note that it is the <code>k<sup>th</sup></code> smallest element <strong>in the sorted order</strong>, not the <code>k<sup>th</sup></code> <strong>distinct</strong> element.</p>

<p>You must find a solution with a memory complexity better than <code>O(n<sup>2</sup>)</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> 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,<u><strong>13</strong></u>,15], and the 8<sup>th</sup> smallest number is 13
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == matrix.length == matrix[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 300</code></li>
	<li><code>-10<sup>9</sup> &lt;= matrix[i][j] &lt;= 10<sup>9</sup></code></li>
	<li>All the rows and columns of <code>matrix</code> are <strong>guaranteed</strong> to be sorted in <strong>non-decreasing order</strong>.</li>
	<li><code>1 &lt;= k &lt;= n<sup>2</sup></code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong></p>

<ul>
	<li>Could you solve the problem with a constant memory (i.e., <code>O(1)</code> memory complexity)?</li>
	<li>Could you solve the problem in <code>O(n)</code> time complexity? The solution may be too advanced for an interview but you may find reading <a href="http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf" target="_blank">this paper</a> fun.</li>
</ul>

#pragma GCC optimize("Ofast")
static auto _ = [](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    struct Data {
        std::size_t row = 0;
        std::size_t col = 0;
        int value = 0;

        friend bool operator<(const Data& d1, const Data& d2) {
            return d1.value >= d2.value;
        }
    };

    int kthSmallest(std::vector<std::vector<int>>& matrix, int k) {
        const auto n = matrix.size();

        std::priority_queue<Data> pq;
        for (std::size_t r = 0; r < std::min<std::size_t>(n, k); ++r) {
            pq.push({ r, std::size_t(0), matrix[r][0] });
        }

        auto data = pq.top();
        while (k--) {
            data = pq.top();
            pq.pop();

            if (data.col != n - 1) {
                pq.push({ data.row, data.col + 1, matrix[data.row][data.col + 1] });
            }
        }

        return data.value;

        /*
        const auto n = matrix.size();

        auto compare = [&](const auto& a, const auto& b) {
            const auto v1 = matrix[a.first][a.second];
            const auto v2 = matrix[b.first][b.second];
            if (v1 == v2) {
                return a > b;
            }
            return v1 > v2;
        };

        using PairT = std::pair<std::size_t, std::size_t>;
        std::priority_queue<PairT, std::vector<PairT>, decltype(compare)> pq(compare);
        pq.push({0, 0});

        auto p = pq.top();
        while (k--) {
            p = pq.top();

            if (p.first != n - 1) {
                pq.push({p.first + 1, p.second});
            }

            if (p.second != n - 1) {
                pq.push({p.first, p.second + 1});
            }

            while (!pq.empty() && p == pq.top()) {
                pq.pop();
            }
        }

        return matrix[p.first][p.second];
        */
    }
};

/*

[[1,8],[4,9]]
1
[[1,8],[4,9]]
2
[[1,8],[4,9]]
3
[[1,8],[4,9]]
4
[[-5]]
1



[[1,5,9],[10,11,13],[12,13,15]]
8
[[1,1,1],[2,2,2],[3,3,3]]
8
[[1,5,10],[4,8,20],[10,18,30]]
7
[[2,5,10],[2,6,11],[3,7,12]]
7
[[1,50,70],[2,60,80],[3,90,100]]
5
[[1,4,30],[2,20,40],[50,60,90]]
6
[[1,2,3],[4,5,6],[10,20,30]]
7
[[1,2,6],[4,5,8],[10,20,30]]
7


[[1,5,6,7],[2,8,11,12],[3,9,13,15],[4,10,14,16]]
1
[[1,5,6,7],[2,8,11,12],[3,9,13,15],[4,10,14,16]]
2
[[1,5,6,7],[2,8,11,12],[3,9,13,15],[4,10,14,16]]
4
[[1,5,6,7],[2,8,11,12],[3,9,13,15],[4,10,14,16]]
6
[[1,5,6,7],[2,8,11,12],[3,9,13,15],[4,10,14,16]]
8
[[1,5,6,7],[2,8,11,12],[3,9,13,15],[4,10,14,16]]
10
[[1,5,6,7],[2,8,11,12],[3,9,13,15],[4,10,14,16]]
12
[[1,5,6,7],[2,8,11,12],[3,9,13,15],[4,10,14,16]]
14


[[1,2,4,6],[3,8,11,12],[5,9,13,15],[7,10,14,16]]
1
[[1,2,4,6],[3,8,11,12],[5,9,13,15],[7,10,14,16]]
3
[[1,2,4,6],[3,8,11,12],[5,9,13,15],[7,10,14,16]]
5
[[1,2,4,6],[3,8,11,12],[5,9,13,15],[7,10,14,16]]
7
[[1,2,4,6],[3,8,11,12],[5,9,13,15],[7,10,14,16]]
9
[[1,2,4,6],[3,8,11,12],[5,9,13,15],[7,10,14,16]]
11
[[1,2,4,6],[3,8,11,12],[5,9,13,15],[7,10,14,16]]
13
[[1,2,4,6],[3,8,11,12],[5,9,13,15],[7,10,14,16]]
15

*/


/*

 1  5  6  7
 2  8 11 12
 3  9 13 15
 4 10 14 16

 1  4  5  6
 2  8 11 12
 3  9 13 15
 7 10 14 16

 1  2  5  6
 3  8 11 12
 4  9 13 15
 7 10 14 16

 1  2  4  6
 3  8 11 12
 5  9 13 15
 7 10 14 16

1 [2, 3]
2 [3, 4, 8]
3 [4, 5, 8]
4 [5, 6, 8, 11]
5 [6, 7, 8, 9, 11]
6 [7, 8, 9, 11, 12]
7 [8, 9, 10, 11, 12]
8 [9, 10, 11, 12]
9 [10, 11, 12, 13]
10 [11, 12, 13, 14]
11 [12, 13, 14]
12 [13, 14, 15]



 1  5  9 20
 2  6 10 21
 3  7 11 22
 4  8 12 23

 1  5  9
10 11 13
12 13 15

 1  5  9
 6  7 10
12 13 15

 1  5 10
 4  8 20
10 18 30


 1 50 70
 2 60 80
 3 90 100

  1  4 30
  2 20 40
 50 60 90


 1  2  3
 4  5  6
10 20 30

 1  2  6
 4  5  8
10 20 30

 1  8  9
 4  9 10
10 20 30

[[1,8,9],[4,9,10],[10,20,30]]

*/
16200