Kth Largest in a Stream (Online)

▶

Steps

setup

Initialize heap with all nums

We start by placing all elements from nums [4, 5, 8, 2] into the heap array and then heapify it to form a valid min-heap.

💡 Heapifying the initial array organizes elements so the smallest is at the root, preparing for efficient kth largest tracking.

Line:

self.heap = nums
heapq.heapify(self.heap)

💡 Heapify transforms an unordered array into a min-heap in O(n) time, setting the foundation for the algorithm.

shrink

Remove smallest elements until heap size is k

Since the heap size (4) is greater than k (3), we pop the smallest element (root) to reduce heap size to k.

💡 Removing the smallest elements ensures the heap only contains the top k largest elements from nums.

Line:

while len(self.heap) > k:
    heapq.heappop(self.heap)

💡 By popping the root, we discard elements smaller than the kth largest candidate.

compare

Add value 3: heap size is k, compare with root

We consider adding 3. Since heap size is already k, we compare 3 with the root (4) to decide if it should replace the root.

💡 Only values larger than the root can affect the kth largest element, so comparison is crucial.

Line:

elif val > self.heap[0]:

💡 Values smaller or equal to the kth largest do not change the heap or kth largest element.

replace

Add value 5: larger than root, replace root

5 is greater than the root (4), so we replace the root with 5 and heapify down to maintain min-heap.

💡 Replacing root updates the kth largest element to a larger value, reflecting the new stream state.

Line:

heapq.heapreplace(self.heap, val)

💡 Heapreplace efficiently removes the smallest and inserts the new value in one operation.

replace

Add value 10: larger than root, replace root

10 is greater than root (5), so replace root with 10 and heapify down to maintain heap property.

💡 Adding a much larger value pushes the kth largest element higher, demonstrating dynamic updates.

Line:

heapq.heapreplace(self.heap, val)

💡 Heap structure adjusts to keep the smallest of the top k largest at root.

replace

Add value 9: larger than root, replace root

9 is greater than root (5), so replace root with 9 and heapify down to maintain min-heap.

💡 Replacing root with 9 shows how the kth largest element can increase gradually.

Line:

heapq.heapreplace(self.heap, val)

💡 Heap adjusts to keep the smallest of the top k largest at root.

compare

Add value 4: smaller than root, ignore

4 is smaller than root (8), so it is ignored and heap remains unchanged.

💡 Ignoring smaller values prevents unnecessary heap operations and keeps kth largest stable.

Line:

elif val > self.heap[0]:

💡 Only values larger than kth largest affect the heap.

peek

Return kth largest after initialization

After initialization, the kth largest element is the root of the heap, which is 4.

💡 The root of the min-heap always represents the kth largest element at any point.

Line:

return self.heap[0]

💡 Initial kth largest is correctly identified from the heap root.

peek

Return kth largest after add(3)

After adding 3 (ignored), the kth largest remains the root 4.

💡 Add operations that do not affect the heap keep the kth largest stable.

Line:

return self.heap[0]

💡 Heap root remains the kth largest after no change.

peek

Return kth largest after add(5)

After adding 5 (replaced root), the kth largest is updated to 5 at the root.

💡 Heap root updates reflect changes in kth largest after insertions.

Line:

return self.heap[0]

💡 Heap root tracks kth largest dynamically.

peek

Return kth largest after add(10)

After adding 10 (replaced root), kth largest remains 5 at the root.

💡 Even large additions may not increase kth largest if heap structure keeps root minimal.

Line:

return self.heap[0]

💡 Heap root is smallest of top k, not necessarily the largest added.

peek

Return kth largest after add(9)

After adding 9 (replaced root), kth largest updates to 8 at the root.

💡 Heap root updates as new larger values push out smaller ones.

Line:

return self.heap[0]

💡 Heap root reflects the current kth largest after dynamic updates.

peek

Return kth largest after add(4)

After adding 4 (ignored), kth largest remains 8 at the root.

💡 Adds smaller than kth largest do not affect the heap or kth largest.

Line:

return self.heap[0]

💡 Heap root remains stable when additions are too small.

import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k  # STEP 1
        self.heap = nums  # STEP 1
        heapq.heapify(self.heap)  # STEP 1
        while len(self.heap) > k:  # STEP 2
            heapq.heappop(self.heap)  # STEP 2

    def add(self, val: int) -> int:
        if len(self.heap) < self.k:  # STEP 3
            heapq.heappush(self.heap, val)  # STEP 3
        elif val > self.heap[0]:  # STEP 4
            heapq.heapreplace(self.heap, val)  # STEP 4
        return self.heap[0]  # STEP 5

# Driver code
if __name__ == '__main__':
    kthLargest = KthLargest(3, [4, 5, 8, 2])  # STEP 1-2
    print(kthLargest.add(3))  # STEP 3,5
    print(kthLargest.add(5))  # STEP 4,5
    print(kthLargest.add(10)) # STEP 4,5
    print(kthLargest.add(9))  # STEP 4,5
    print(kthLargest.add(4))  # STEP 3,5

📊

Kth Largest in a Stream (Online) - Watch the Algorithm Execute, Step by Step

Watching each heap operation and decision helps you understand how the algorithm efficiently keeps track of the kth largest element without sorting the entire stream.

heapifymin-heap

2

0

4

1

8

2

5

3

extract_minmin-heap

4

0

5

1

8

2

peekmin-heap

4

0

5

1

8

2

Added: 4

heapify_downmin-heap

5

0

5

1

8

2

Added: 5

heapify_downmin-heapswap [0↔2]

5

0

10

1

8

2

Added: 5

heapify_downmin-heapswap [0↔2]

8

0

10

1

9

2

Added: 8

peekmin-heap

8

0

10

1

9

2

Added: 8

peekmin-heap

4

0

5

1

8

2

Added: 4

peekmin-heap

4

0

5

1

8

2

Added: 4

peekmin-heap

5

0

5

1

8

2

Added: 5

peekmin-heap

5

0

10

1

8

2

Added: 5

peekmin-heap

8

0

10

1

9

2

Added: 8

peekmin-heap

8

0

10

1

9

2

Added: 8

Key Takeaways

✓ Maintaining a min-heap of size k efficiently tracks the kth largest element in a stream.

This insight is hard to see from code alone because the heap operations and their effect on the kth largest element are abstract without visualization.

✓ Only values larger than the current kth largest (heap root) affect the heap, minimizing unnecessary operations.

Visualizing each comparison and decision clarifies why some adds are ignored and others cause heap updates.

✓ The root of the min-heap always holds the kth largest element, even as the heap contents change dynamically.

Seeing the root update step-by-step helps understand the heap invariant and its role in the algorithm.

Practice

1. Consider the following Python code implementing the heap-based approach to find the k-th smallest pair distance. What is the returned value when calling smallestDistancePair([1,3,1], 2)?

easy

A. 3

B. 1

C. 0

D. 2

Solution

1. Step 1: Sort input and initialize heap

   Sorted nums = [1,1,3]. Initial heap contains pairs: (0,0,1), (2,1,2).

2. Step 2: Pop k-1=1 times and push next pairs

   Pop (0,0,1). Since j+1=2<n, push (3-1=2,0,2). Heap now: (2,0,2), (2,1,2). The smallest distance at heap top is 2.

3. Step 3: Return the k-th smallest distance

   After popping once, the top of the heap is (2,0,2), so the returned value is 2.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Second smallest pair distance is 2 [OK]

Hint: Trace heap pops and pushes carefully for small inputs [OK]

Common Mistakes:

• Off-by-one in k-1 loop
• Confusing indices i,j
• Returning wrong heap element

2. Consider the following code snippet for finding the kth largest XOR coordinate value. Given the input matrix = [[5, 2], [1, 6]] and k = 3, what is the value of min_heap[0] returned by the function?

easy

A. 4

B. 5

C. 6

D. 7

Solution

1. Step 1: Compute prefix XOR matrix values

   prefix[1][1] = 5, prefix[1][2] = 7 (5^2), prefix[2][1] = 4 (5^1^0), prefix[2][2] = 0 (prefix[1][2]^prefix[2][1]^prefix[1][1]^matrix[1][1] = 7^4^5^6 = 0)

2. Step 2: Track min_heap of size k=3

   Values inserted: 5, 7, 4. The heap after these is [4,7,5]. The next value 0 is less than min_heap[0]=4, so ignored. The kth largest is min_heap[0] = 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap after all insertions has 4 as smallest among top 3 [OK]

Hint: Trace prefix XOR and heap insertions carefully [OK]

Common Mistakes:

• Off-by-one in prefix indices
• Miscomputing XOR values
• Confusing heap root with max value

3. Consider the following Python code implementing the optimal approach to find the kth smallest element in a sorted matrix. Given the matrix [[1,5],[6,10]] and k = 3, what is the final returned value?

easy

A. 6

B. 5

C. 10

D. 1

Solution

1. Step 1: Trace countLessEqual(mid) for mid=5

   Count elements ≤5: row=1,col=0; matrix[1][0]=6>5 -> row=0; matrix[0][0]=1≤5 -> count=1, col=1; matrix[0][1]=5≤5 -> count=2, col=2 (end). Total=2 < k=3.

2. Step 2: Update low=mid+1=6, repeat binary search

   Now low=6, high=10; mid=8; countLessEqual(8) counts elements ≤8: row=1,col=0; matrix[1][0]=6≤8 -> count=2, col=1; matrix[1][1]=10>8 -> row=0; matrix[0][1]=5≤8 -> count=3, col=2 (end). Total=3 ≥ k=3, so high=mid=8.

3. Step 3: Continue binary search until low=high=6

   Eventually low converges to 6, which is the 3rd smallest element.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Binary search narrows to 6 as 3rd smallest [OK]

Hint: Count elements ≤ mid guides binary search [OK]

Common Mistakes:

• Off-by-one in k indexing
• Miscounting elements ≤ mid

4. Suppose the problem changes: now characters can be reused unlimited times (like infinite supply), and you want to return a string of length k with characters sorted by frequency descending. Which modification to the bucket sort approach correctly handles this variant?

hard

A. Use a max heap to repeatedly extract the highest frequency character and append it until length k is reached, decrementing frequency each time.

B. Use the same bucket sort but truncate the final concatenated string to length k.

C. Use bucket sort but repeat characters infinitely in buckets until length k is reached.

D. Sort characters by frequency once, then repeat the entire sorted string until length k is reached.

Solution

1. Step 1: Understand infinite reuse constraint

   Characters can be used multiple times, frequencies decrease as used.

2. Step 2: Why max heap is needed

   Max heap allows extracting highest frequency char, appending it, then updating frequency dynamically.

3. Step 3: Why bucket sort fails here

   Bucket sort assumes fixed frequencies; infinite reuse requires dynamic frequency updates.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Max heap supports dynamic frequency changes and repeated extraction [OK]

Hint: Infinite reuse needs dynamic frequency updates, not static buckets [OK]

Common Mistakes:

• Truncating static bucket sort output
• Repeating entire sorted string ignoring frequencies

5. Suppose you want to find the top k frequent words but now words can be reused infinitely many times (like unlimited supply). Which modification to the optimal bucket sort approach correctly handles this scenario?

hard

A. This problem reduces to a knapsack variant; bucket sort no longer applies

B. Modify frequency counting to consider infinite reuse, then apply bucket sort as usual

C. Use a dynamic programming approach to count combinations of words for frequencies

D. Use a max heap keyed by frequency and word lex order, repeatedly pop top k elements

Solution

1. Step 1: Understand infinite reuse impact

   Infinite reuse means frequency counts are not fixed; problem becomes combinatorial.

2. Step 2: Recognize problem class change

   Top k frequent words with unlimited reuse resembles knapsack or coin change, not simple frequency counting.

3. Step 3: Bucket sort no longer applies

   Bucket sort relies on fixed frequencies; dynamic programming or other combinatorial methods are needed.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Infinite reuse breaks frequency counting assumptions [OK]

Hint: Infinite reuse changes problem class, bucket sort invalid [OK]

Common Mistakes:

• Trying to reuse bucket sort with infinite counts
• Ignoring combinatorial explosion
• Assuming heap approach suffices