Skip to content

Volume ITechnology

4.17.1 — Kth Largest Element in a Stream ​

LeetCode 703 · Easy

The problem ​

Build a class that keeps track of the k-th largest value seen so far. It is created with k and a starting list nums. Then values arrive one at a time through add(val), and every call to add returns the current k-th largest value.

KthLargest(3, [4, 5, 8, 2])
add(3)   →  4      values so far: 2 3 4 5 8, the 3rd largest is 4
add(5)   →  5      2 3 4 5 5 8, the 3rd largest is 5
add(10)  →  5      2 3 4 5 5 8 10, the 3rd largest is 5
add(9)   →  8
add(4)   →  8

Repeats count separately. In 5 5 8, the two 5s are the 2nd and 3rd largest. k is at most 10,000, and there are up to 10,000 calls to add.

What the problem is really asking ​

Look at what happens to a small value. Once a value is not among the k largest, can it ever get back in? No. New values can only push it further down the ranking. So it can be thrown away forever.

That means you never need more than the k largest values. And the answer, the k-th largest, is simply the smallest of those k.

So the real question is: how do you keep the k largest values, and always see the smallest of them instantly?

The brute force, and where it wastes work ​

Keep every value in a list, and sort it on each call.

python
class KthLargest:
    def __init__(self, k, nums):
        self.k, self.vals = k, list(nums)
    def add(self, val):
        self.vals.append(val)
        self.vals.sort(reverse=True)        # biggest first
        return self.vals[self.k - 1]

Each call sorts everything seen so far, which is O(n \log n) per call, and the list grows forever.

The waste in one sentence: it keeps and re-sorts every value, when only the k largest can ever matter.

The idea ​

Keep exactly k values in a min-heap. A min-heap is a structure that always keeps its smallest item at the front, where you can read it instantly. Adding an item, or removing the smallest, takes O(\log m) steps for a heap of m items. Python's heapq module provides one. 4.16 explains how it works.

Why a heap that keeps the smallest at the front, when we want the largest values? Because the item we keep needing to reach is the weakest of the k we are keeping. It is both the answer, and the one a bigger newcomer pushes out.

For each new value:

  1. Push it into the heap.
  2. If the heap now holds more than k values, remove the smallest. It is no longer in the top k.
  3. The smallest remaining value is the answer.

The solution ​

python
import heapq

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

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)                # (5)
        if len(self.heap) > self.k:                   # (6)
            heapq.heappop(self.heap)
        return self.heap[0]                           # (7)
ts
// TypeScript has no built-in heap. MinHeap is the class built in 4.16:
// push(x), pop() removes the smallest, peek() reads it, size counts items.
class KthLargest {
  private heap = new MinHeap<number>();
  constructor(private k: number, nums: number[]) {   // (1)
    for (const n of nums) {                          // (2)
      this.heap.push(n);                             // (3)
      if (this.heap.size > k) this.heap.pop();       // (4)
    }
  }

  add(val: number): number {
    this.heap.push(val);                             // (5)
    if (this.heap.size > this.k) this.heap.pop();    // (6)
    return this.heap.peek()!;                        // (7)
  }
}

Line by line ​

(1) Remember k. add needs it later.

(2) Copy the starting values. nums[:] makes a copy, so we never change the caller's list.

(3) Turn the copy into a heap. heapify rearranges a list into heap order in place. It takes O(n) time, which is faster than pushing the values one at a time. TypeScript pushes them one at a time, which also works.

(4) Throw away everything below the top k. While there are too many values, remove the smallest.

(5) Add the new value.

(6) Too many values now? Remove the smallest. It might be the value just added, if that value was too small to make the top k.

(7) The smallest value in the heap is the k-th largest overall. In Python, heap[0] is always the smallest item of a heap.

Trace ​

KthLargest(3, [4, 5, 8, 2]). The heap is shown as a sorted list so it is easy to read.

StepHeap after pushToo many?Heap afterReturns
start[2, 4, 5, 8]4 > 3, remove 2[4, 5, 8]—
add(3)[3, 4, 5, 8]remove 3[4, 5, 8]4
add(5)[4, 5, 5, 8]remove 4[5, 5, 8]5
add(10)[5, 5, 8, 10]remove 5[5, 8, 10]5
add(9)[5, 8, 9, 10]remove 5[8, 9, 10]8
add(4)[4, 8, 9, 10]remove 4[8, 9, 10]8

Complexity, derived ​

Setup. heapify is O(n). Then up to n - k pops, each O(\log n). So the setup is O(n \log n) in the worst case.

Each add. One push and at most one pop on a heap of at most k + 1 items. Each costs O(\log k). So add is O(\log k).

Space. The heap never holds more than k + 1 values, so O(k).

Edge cases ​

  • The starting list has fewer than k values. The problem promises that by the time the answer is needed, there are at least k. Until then the heap is simply small, and line (6) never removes anything.
  • Repeated values. They are separate items in the heap, so they count separately, as the problem wants.
  • A very small new value. It is pushed and then immediately removed in line (6).

Why not sort, and why not keep everything in a heap ​

Sorting on every call is O(n \log n) per call and stores everything.

A heap of all values is O(\log n) per push but O(n) memory. Finding the k-th largest would mean removing k items and putting them back.

A heap of size k is O(\log k) per call and O(k) memory, and the answer is always at the front. Since k is usually much smaller than n, this wins on both time and memory.

The general lesson: throw away anything that can never be part of the answer, as early as you can. It is the same instinct as the run-start check in 4.4.9 and the eviction rule of a monotonic stack.

Variations you will meet ​

  • Top K Frequent Elements. The same size-k heap, over counts. See 4.4.5.
  • K Closest Points to Origin. A size-k heap over distances, but now you want the k smallest, so the heap must keep the biggest at the front. See 4.17.3.
  • Find Median from Data Stream. Two heaps facing each other. See 4.17.7.
  • Real reports, like "the 10 slowest web requests today" or "the 100 largest files". All use a size-k heap, because the full data is too big to keep.

What the interviewer will push on ​

"Min-heap or max-heap, and why?" A min-heap for the k largest. Its front is the one you throw out.

"Why not keep everything sorted?" O(n \log n) per call and memory that grows forever.

"What if k is close to the total number of values?" The heap stops saving much, because \log k approaches \log n. Sorting once and inserting carefully becomes competitive.

"Why is heapify O(n) and not O(n \log n)?" Most items in a heap sit near the bottom, where there is almost no room to move down. Adding up the small amounts of work gives O(n). 4.16 shows the sum.

One thing to volunteer: say why a value outside the top k can be thrown away forever. That one sentence is the whole design.

Next: 4.17.2 Last Stone Weight. A simulation where a heap is the obvious tool.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet