#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/heap-priority-queue/kth-largest-element-in-a-stream-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/heap-priority-queue/kth-largest-element-in-a-stream-implementation

Repovive

LeetCode 703 Kth Largest Element in a Stream - Implementation - Heap / Priority Queue | Pattern 22: LeetCode Interview Patterns | Repovive

Repovive.

Pattern 22: LeetCode Interview Patterns24 sections · 736 units32h total

Open in Course

LeetCode 703 Kth Largest Element in a Stream - Implementation

The approach

Min-heap of size k. Return heap minimum after each add.

class KthLargest: def init(self, k, nums): self.k = k self.heap = [] for num in nums: self.add(num)

def add(self, val):
    if len(self.heap) < self.k:
        heappush(self.heap, val)
    elif val > self.heap[0]:
        heapreplace(self.heap, val)
    return self.heap[0]

$O(\log k)$ per add, $O(k)$ space.