Learn › DSA Patterns › Top K Elements › Case Study
Top K Frequent Elements:
6 Bugs Building a Heap From Scratch
Not a tutorial — a real debugging log. TypeScript has no built-in heap, so this journey hand-builds one, hits six distinct bugs along the way, and fixes each with a concrete compiler error before moving on.
The Problem
LeetCode 347 — Top K Frequent Elements
Given an integer array nums and an integer
k, return the k most
frequent elements. You may return the answer in any order.
Input
nums = [1,1,1,2,2,3], k = 2 Output
[1,2] Input
nums = [1], k = 1 Output
[1] The Journey
Attempt by Attempt
Every bug below is a real compiler error, reproduced before being fixed — not just described after the fact.
push(item): void {
heap.push(item)
let i = size() - 1
while (i > 0) {
let parentIndex = floor((i - 1) / 2)
if (heap[i].count < heap[parentIndex].count) {
swap(heap[i], heap[parentIndex])
i = parentIndex
} else break
}
}Four separate mistakes fire at once — three missing `this.`, a lowercase `floor`, tuple values read like object properties, and a helper called with the wrong kind of argument.
heap, size(), and swap() are all members of the MinHeap class — outside a method body they need the this. prefix, or TypeScript can't find them at all. floor isn't a global function in TypeScript; only Math.floor exists. And since heap is typed as [number, number][] — an array of tuples, not objects — heap[i].count doesn't exist; the count lives at index [0]. On top of all that, swap was written to take two array indices, but this call hands it the values stored at those indices instead.
Proof — tsc --strict --noEmit output:
error TS2304: Cannot find name 'heap'. error TS2304: Cannot find name 'size'. error TS2304: Cannot find name 'floor'. error TS2339: Property 'count' does not exist on type '[number, number]'. error TS2345: Argument of type '[number, number]' is not assignable to parameter of type 'number'.
Prefix every member access with this., swap floor for Math.floor, replace .count with index access [0], and call this.swap(i, parentIndex) — indices, not values.
push(item: [number, number]): void {
this.heap.push(item);
let i = this.size() - 1;
while (i > 0) {
let parentIndex = Math.floor((i - 1) / 2);
if (this.heap[i][0] < this.heap[parentIndex][0]) {
this.swap(i, parentIndex);
i = parentIndex;
} else break;
}
}Every fix from Attempt 1 applied together: this. on every member access, Math.floor for the parent-index formula, [0] to read the frequency out of the [count, num] tuple, and swap(i, parentIndex) passing indices already in scope instead of the values stored there.
Proof — hand trace, pushing (3,1) → (2,2) → (1,3):
push([3,1]) → heap: [[3,1]] push([2,2]) → bubbles up → heap: [[2,2],[3,1]] push([1,3]) → bubbles up → heap: [[1,3],[3,1],[2,2]] Min-heap property holds at every step — smaller count always sits above its parent.
pop() {
if (this.heap.length === 0) return undefined
const min = this.heap[0]
const last = this.heap.pop()
if (this.heap.length > 0) {
this.heap[0] = last
this.bubbleDown(0)
}
return min;
}Compiles-clean logic, but TypeScript's own type system blocks the assignment.
Array.prototype.pop() is typed to return T | undefined, because an empty array has nothing to pop. Even though the if (this.heap.length === 0) guard above means last can never actually be undefined at the point it's used, TypeScript's checker doesn't trace that guard forward to a later, unrelated line. Assigning a possibly-undefined value into a slot typed as a definite tuple fails to compile.
Proof — tsc --strict --noEmit output:
error TS2322: Type '[number, number] | undefined' is not assignable to type '[number, number]'.
Add a non-null assertion: const last = this.heap.pop()! — telling TypeScript the guard above already ruled out undefined.
toArray(): [number] {
return this.heap.map(([count, num]) => num)
}
// ⚠ an earlier draft of this same line was annotated [number, number][] instead —
// wrong in a different way, but still not "an array of numbers, any length"The method's logic is correct, but its return type annotation lies about what it returns — in two different ways, back to back.
The .map(([count, num]) => num) callback returns a plain number for each entry, so the array produced is number[] — a list of any length. The first draft annotated it as [number, number][] (an array of two-element tuples, left over from copying the field's own type). The very next fix swapped to [number], which looks close but means something else again: a tuple with exactly one number, not an array of any length.
Proof — tsc --strict --noEmit output:
error TS2322: Type 'number[]' is not assignable to type '[number]'. Target requires 1 element(s) but source may have more.
The correct annotation is simply number[] — an array of numbers, any length.
// top of the file — added silently by editor autocomplete
import { MinHeap } from "some-heap-library";
// further down — the hand-written implementation this journey actually built
class MinHeap {
// ...
}A name collision introduced by the editor, not by any line actually typed on purpose.
Autocomplete silently inserted an import { MinHeap } from '...' line the moment new MinHeap() was typed, against some installed package that happened to export something with the same name. TypeScript then found two different things both named MinHeap in one file and refused to pick a winner.
Proof — tsc --strict --noEmit output:
error TS2440: Import declaration conflicts with local declaration of 'MinHeap'.
Delete the stray auto-inserted import — the hand-built class is the one actually meant to run — or rename the class if the import is genuinely needed for something else.
// O(N log K) — only ever keeps K entries in the heap at once
class MinHeap {
private heap: [number, number][] = []; // [count, num]
push(item: [number, number]): void {
this.heap.push(item);
let i = this.size() - 1;
while (i > 0) {
const p = Math.floor((i - 1) / 2);
if (this.heap[i][0] >= this.heap[p][0]) break;
this.swap(i, p);
i = p;
}
}
pop(): [number, number] | undefined {
if (this.heap.length === 0) return undefined;
const min = this.heap[0];
const last = this.heap.pop()!;
if (this.heap.length > 0) {
this.heap[0] = last;
this.bubbleDown(0);
}
return min;
}
private bubbleDown(i: number): void {
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let smallest = i;
if (l < this.heap.length && this.heap[l][0] < this.heap[smallest][0]) smallest = l;
if (r < this.heap.length && this.heap[r][0] < this.heap[smallest][0]) smallest = r;
if (smallest === i) break;
this.swap(i, smallest);
i = smallest;
}
}
private swap(i: number, j: number): void {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
size(): number { return this.heap.length; }
toArray(): number[] { return this.heap.map(([, num]) => num); }
}
// LeetCode 347
function topKFrequent(nums: number[], k: number): number[] {
const freqMap = new Map<number, number>();
for (const num of nums) freqMap.set(num, (freqMap.get(num) || 0) + 1);
const heap = new MinHeap();
for (const [num, count] of freqMap) {
heap.push([count, num]);
if (heap.size() > k) heap.pop();
}
return heap.toArray();
}Every fix from every attempt applied together: this. everywhere, Math.floor for parent indices, [0]/index access instead of .count/.num, swap(i, j) by index, a non-null assertion on pop()'s popped element, number[] on toArray(), and the stray auto-import removed.
Proof — full trace against nums=[1,1,1,2,2,3], k=2:
freq map: {1:3, 2:2, 3:1}
push [3,1] → heap [[3,1]]
push [2,2] → heap [[2,2],[3,1]]
push [1,3] → heap [[1,3],[3,1],[2,2]], size 3 > 2 → pop()
pop(): removes [1,3], moves [2,2] to root, bubbles down (no swap needed)
final heap: [[2,2],[3,1]] → toArray() → [2, 1]
Expected: {1, 2} in any order — MATCH ✅ Interactive
Heap Visualizer
Watch the size-2 min-heap build against nums = [1,1,1,2,2,3], k = 2 —
each node shows freq, num.
Heap empty — press Step Forward to begin.
Lessons Learned
Key Takeaways
Tuples aren't objects — index, don't dot
When heap is typed [number, number][], values live at [0] / [1]. .count / .num compiles fine in loosely-typed JavaScript, but TypeScript's tuple types reject it outright — the compiler catches the mix-up before the code ever runs.
A helper's parameters are a contract
swap(i, j) was written to take array indices. Handing it the values stored at those indices instead — swap(heap[i], heap[j]) — is a type mismatch, not a stylistic choice, and TypeScript flags it immediately.
Derive the parent formula, don't memorize it
Children of node i always sit at 2i+1 and 2i+2. Solving either equation for the parent and letting Math.floor collapse both cases into one removes the need to memorize any index math at all.
.pop() can return undefined — even when logic rules it out
TypeScript types Array.prototype.pop() as T | undefined unconditionally. A guard written earlier in the same function doesn't change that type for TypeScript's checker; only a non-null assertion or an explicit re-check does.
[number] and number[] are not the same type
One is a tuple that must hold exactly one element. The other is an array of any length. Mixing them up produces a compile error that reads deceptively close to correct — this journey hit both variants back to back.
Editor auto-import can create a collision you never typed
If an installed package happens to export something sharing a name with a class being written from scratch, autocomplete can silently import it — producing a TS2440 error far from where the real mistake actually is.
Final Result
Two Verified Solutions
Both pass every test case in this journey — pick based on how small k is relative to n.
// O(N log N) — sorts every unique count, even when k is tiny
function topKFrequent(nums: number[], k: number): number[] {
const freqMap = new Map<number, number>();
for (const num of nums) freqMap.set(num, (freqMap.get(num) || 0) + 1);
return [...freqMap.entries()]
.sort((a, b) => b[1] - a[1])
.slice(0, k)
.map(([num]) => num);
}// O(N log K) — only ever keeps K entries in the heap at once
class MinHeap {
private heap: [number, number][] = []; // [count, num]
push(item: [number, number]): void {
this.heap.push(item);
let i = this.size() - 1;
while (i > 0) {
const p = Math.floor((i - 1) / 2);
if (this.heap[i][0] >= this.heap[p][0]) break;
this.swap(i, p);
i = p;
}
}
pop(): [number, number] | undefined {
if (this.heap.length === 0) return undefined;
const min = this.heap[0];
const last = this.heap.pop()!;
if (this.heap.length > 0) {
this.heap[0] = last;
this.bubbleDown(0);
}
return min;
}
private bubbleDown(i: number): void {
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let smallest = i;
if (l < this.heap.length && this.heap[l][0] < this.heap[smallest][0]) smallest = l;
if (r < this.heap.length && this.heap[r][0] < this.heap[smallest][0]) smallest = r;
if (smallest === i) break;
this.swap(i, smallest);
i = smallest;
}
}
private swap(i: number, j: number): void {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
size(): number { return this.heap.length; }
toArray(): number[] { return this.heap.map(([, num]) => num); }
}
// LeetCode 347
function topKFrequent(nums: number[], k: number): number[] {
const freqMap = new Map<number, number>();
for (const num of nums) freqMap.set(num, (freqMap.get(num) || 0) + 1);
const heap = new MinHeap();
for (const [num, count] of freqMap) {
heap.push([count, num]);
if (heap.size() > k) heap.pop();
}
return heap.toArray();
}| Solution | Time | Space | Verified |
|---|---|---|---|
| Brute Force (Sort) | O(N log N) | O(N) | Sorts every unique count |
| Min-Heap (Size k) Optimized ✓ | O(N log K) | O(N + K) | 6-bug journey + hand trace |
Reuse This
Template: Top K via Size-Capped Min-Heap
The generic shape behind this solution — adapt it to any "give me the k best" problem.
function topK(items, k, priority):
heap = new MinHeap() // ordered ascending by priority
for item in items:
heap.push(item)
if heap.size() > k:
heap.pop() // discard the lowest-priority survivor
return heap.toArray() // whatever remains are the k highest-priority itemsWhen to reach for this
Any "give me the k biggest / most-frequent / closest" question where k stays much smaller than the input — top-k frequent elements, k closest points, kth largest in a stream.
The trap this journey hit
In a language with no built-in heap, every operation — push, pop, the index math — has to be handwritten and type-checked correctly before the algorithm itself even runs.
Test Yourself
Quiz: Check Your Understanding
Your score
0 / 5
Keep Learning
Bugs are part of the process 🎉
Six real bugs, six real fixes — that's what building a data structure from scratch, in a language that doesn't hand you one, actually looks like.