<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>

class Solution {
public:
    int n;
    int encode(int row, int col)
    {
        return row * n + col;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        // Create a min heap
        // Add the corner element to the heap. This is garunteed to be the smallest number.
        // For each iteration: Pop the smallest element from the heap. The next smallest element will be either the stuff currently in the heap or the elements to the left and right

        this->n = matrix.size();
        int numIterations = 0;
        priority_queue< pair<int,pair<int,int>>, 
                        vector<pair<int,pair<int,int>>>, 
                        greater<pair<int,pair<int,int>>> > minHeap; // {integer, {row, col}}
        unordered_set<int> visited;
        minHeap.push({matrix[0][0], {0, 0}});
        visited.insert(encode(0,0));
        int kthSmallestNum = matrix[0][0];
        while(!minHeap.empty())
        {
            auto topHeap = minHeap.top();
            minHeap.pop();
            kthSmallestNum = topHeap.first;
            int row = topHeap.second.first;
            int col = topHeap.second.second;
            numIterations++;
            if(numIterations == k)
            {
                return kthSmallestNum;
            }

            //Right element
            if(col + 1 < n && visited.find(encode(row, col+1)) == visited.end())
            {
                minHeap.push({matrix[row][col+1], {row, col+1}});
                visited.insert(encode(row, col+1));
            }
            
            //Bottom element
            if(row + 1 < n && visited.find(encode(row+1, col)) == visited.end())
            {
                minHeap.push({matrix[row+1][col], {row + 1, col}});
                visited.insert(encode(row+1, col));
            }
            
        }

        return kthSmallestNum;
    }
};
23000