Problem

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

Given anxnmatrix where each of the rows and columns are sorted in ascending order, find 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:

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

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

Solution:

Steps:

1. build heap of size n from first row. each key's value is their coordinate
2. pop min, push the element in the same column of min but one row down. To ensure that heap always pop the smallest K elements.