Python Heap Solution O(klogn*); n* = # of columns


  • 0
    E
        def __lt__(self, other):
            return self[0] < other[0]
            
        def kthSmallest(self, matrix, k):
    
            import heapq
            
            if not matrix or not matrix[0]: return 0
            H = [(v, 0, i) for i,v in enumerate(matrix[0])]
            heapq.heapify(H)
            v = None
            while k > 0:
                v, r, c = heapq.heappop(H)
                _r, k = r + 1, k - 1
                if _r < len(matrix): heapq.heappush(H, (matrix[_r][c], _r, c))
            return v
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.