Easy to understand min-heap(sized k) python solution runtime: O(n * log k), space: O(k)


  • 0
    T
    def findKthLargest(self, nums, k):
        topk = []
        for n in nums:
            if len(topk) == k:
                if n > topk[0]:
                    heapq.heapreplace(topk, n)
            else:
                heapq.heappush(topk, n)
        return topk[0]
    

    keep maintain a sized k min-heap


Log in to reply
 

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