Leetcode 378 Kth Smallest Element in a Sorted Matrix

Given an n x n matrix where each of the rows and columns are sorted in ascending order, return the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13

Input: matrix = [[-5]], k = 1
Output: -5

• Use Heap to solve the question.

• Min Heap (easy understand): Push all values into min heap and pop k-1 value from min heap, then the head of the heap will be the kth element.

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

class Solution:

    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        minHeap = []
        for x in matrix:
            for y in x:
                heapq.heappush(minHeap, y)
        index = 0
        while index<k-1:
            heapq.heappop(minHeap)
            index+=1
        return minHeap[0]