[LeetCode] 378. Kth Smallest Element in a Sorted Matrix

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

This problem equals to merge N sorted lists and find the kth element from the merged list.

Use heap to find small element from N sorted list.

Time complexity = O(K * Log N ), N = len(matrix)

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        heap = []
        
        for i in range(len(matrix)):
            heapq.heappush(heap, (matrix[i][0], i, 0))
        
        result = 0
        for _ in range(k):
            result, y, x = heapq.heappop(heap)
            
            x += 1
            if x < len(matrix[y]):
                heapq.heappush(heap, (matrix[y][x], y, x))
        
        return result