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

  • 0
        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])]
            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.