**Algorithm**

`h`

: list of tuple`(element, row, index)`

, which is initialised with first element of each row in the matrix.- We maintain a heap. In the for loop, we get the smallest element
`v`

which is in row`r`

, and replace`v`

with the next element in the row`r`

**Time Complexity**

- insert an element into heap: O(log(n)), where n is the width of the matrix
- find k the k-th element O(k)
- Overall: O(klog(n))

```
from heapq import heappush, heappop, heapreplace, heapify
class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
h = [(row[0], row, 1) for row in matrix]
heapify(h)
# Since we want to find kth, we pop the first k elements
for _ in xrange(k - 1):
v, r, i = h[0]
if i < len(r):
heapreplace(h, (r[i], r, i + 1))
else:
heappop(h)
return h[0][0]
```