378. Kth Smallest Element in a Sorted Matrix - python3

Given a n x n matrix 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.

My Answer 1: Accepted (Runtime: 172 ms - 74.42% / Memory Usage: 19.9 MB - 67.68%)

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        stack = []
        
        for mat in matrix:
            for i in range(0, len(mat)):
                stack.append(mat[i])
        
        stack.sort()
        
        return stack[k-1]

젤 먼저 든 생각은 역시나 모든 값을 stack 에 저장한 후 sort 하는 방식..^^
생각보다 효율이 좋아서 놀랬다

그리고 k 번째 값이 어디에 위치할지 모르기 때문에 어차피 모든 값을 확인해야해서 괜찮은거 같기도...?

Heap

Solution 1: Runtime: 184 ms - 68.64% / Memory Usage: 20.2 MB - 16.48%

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        a, res = [], -1
        
        for r in matrix:
            for e in r:
                heappush(a, e)

        for _ in range(k):
            res = heappop(a)  
            
        return res

heap a 에 값을 모두 저장하고 k 만큼 pop 해서 k 번째 값을 반환

파이썬은 min-heap (최소 힙) 형태로 저장됨
heappop => 가장 작은 값부터 순서대로 pop

Heap with Python 참고: https://redcrow.tistory.com/487