Tracks

Full-Stack Interview Prep

AI Engineering Roadmap →

Heap

18 problems · 21 approaches

← Checklist · All topics →

Kth largest element in an arrayMedium2 approaches

Problem

Return the kth largest element of an unsorted array — by sorted position, not the kth distinct value.

Example 1

Input:  nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Example 2

Input:  nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4

1. Min-heap of size k

Time O(n log k)Space O(k)

Keep the k largest so far; the heap root is the kth largest. Great for a stream.

class MinHeap {
  constructor() { this.a = []; }
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) { const a = this.a; a.push(x); let i = a.length - 1;
    while (i && a[(i - 1) >> 1] > a[i]) { [a[(i - 1) >> 1], a[i]] = [a[i], a[(i - 1) >> 1]]; i = (i - 1) >> 1; } }
  pop() { const a = this.a, top = a[0], last = a.pop();
    if (a.length) { a[0] = last; let i = 0;
      for (;;) { let s = i, l = 2*i+1, r = 2*i+2;
        if (l < a.length && a[l] < a[s]) s = l;
        if (r < a.length && a[r] < a[s]) s = r;
        if (s === i) break; [a[s], a[i]] = [a[i], a[s]]; i = s; } }
    return top; }
}
function findKthLargest(nums, k) {
  const h = new MinHeap();
  for (const x of nums) { h.push(x); if (h.size > k) h.pop(); }
  return h.peek();
}

2. Quickselect

Time O(n) avgSpace O(1)

Partition for the (n−k)th smallest index. Average O(n), no extra structure.

function findKthLargest(nums, k) {
  const target = nums.length - k;
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const pivot = nums[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) if (nums[j] < pivot) [nums[i], nums[j]] = [nums[j], nums[i]], i++;
    [nums[i], nums[hi]] = [nums[hi], nums[i]];
    if (i === target) return nums[i];
    i < target ? (lo = i + 1) : (hi = i - 1);
  }
  return nums[lo];
}
Implement a binary heap (min & max) with array + sift up/downMedium1 approach

Problem

Implement a binary heap stored in an array (parent at (i−1)/2, children at 2i+1 and 2i+2) with insert, extractMin (or extractMax), peek and heapify, using sift-up and sift-down.

Example 1

Input:  insert 5, 3, 8, 1 → extractMin() → peek()
Output: 1, 3

Also asked as: Implement a Maxheap/MinHeap using arrays and recursion · Convert min heap to max heap

1. Array-backed heap

Time push/pop O(log n), build O(n)Space O(n)

Parent of i is (i−1)>>1; children are 2i+1, 2i+2. push sifts up, pop swaps root with last and sifts down. "Heapify" an arbitrary array by sifting down every non-leaf from the middle back to 0 — that is how you turn a min-heap array into a max-heap.

class Heap {
  constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }   // min-heap by default
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a; a.push(x);
    let i = a.length - 1;
    while (i > 0) { const p = (i - 1) >> 1; if (this.cmp(a[p], a[i]) <= 0) break; [a[p], a[i]] = [a[i], a[p]]; i = p; }
  }
  pop() {
    const a = this.a, top = a[0], last = a.pop();
    if (a.length) { a[0] = last; this.#down(0); }
    return top;
  }
  #down(i) {
    const a = this.a;
    for (;;) {
      let s = i, l = 2 * i + 1, r = 2 * i + 2;
      if (l < a.length && this.cmp(a[l], a[s]) < 0) s = l;
      if (r < a.length && this.cmp(a[r], a[s]) < 0) s = r;
      if (s === i) break;
      [a[s], a[i]] = [a[i], a[s]]; i = s;
    }
  }
  static heapify(arr, cmp) { const h = new Heap(cmp); h.a = arr; for (let i = (arr.length >> 1) - 1; i >= 0; i--) h.#down(i); return h; }
}
// Max-heap: new Heap((a, b) => b - a).
Heap sortMedium1 approach

Problem

Sort an array in place by building a max-heap and then repeatedly swapping the maximum to the end and sifting down. O(n log n) time, O(1) space, not stable.

Example 1

Input:  [12, 11, 13, 5, 6, 7]
Output: [5, 6, 7, 11, 12, 13]

Also asked as: Sort an Array using heap. (HeapSort)

1. Build max-heap in place, repeatedly extract the max to the end

Time O(n log n)Space O(1)

Heapify the array into a max-heap; swap the root with the last unsorted element and sift down the reduced heap. In place, O(1) extra.

function heapSort(a) {
  const n = a.length;
  const down = (i, size) => {
    for (;;) {
      let s = i, l = 2 * i + 1, r = 2 * i + 2;
      if (l < size && a[l] > a[s]) s = l;
      if (r < size && a[r] > a[s]) s = r;
      if (s === i) break;
      [a[s], a[i]] = [a[i], a[s]]; i = s;
    }
  };
  for (let i = (n >> 1) - 1; i >= 0; i--) down(i, n);
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    down(0, end);
  }
  return a;
}
Maximum of all subarrays of size k (sliding window maximum)Medium1 approach

Problem

For every contiguous window of size k, return its maximum. Aim for O(n) overall.

Example 1

Input:  nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]

Also asked as: Maximum of all subarrays of size k

1. Monotonic decreasing deque

Time O(n)Space O(k)

Keep indices whose values are decreasing. Pop smaller values from the back on insert; pop the front when it leaves the window. The front is the current window max.

function maxSlidingWindow(a, k) {
  const dq = [], res = [];
  for (let i = 0; i < a.length; i++) {
    while (dq.length && a[dq[dq.length - 1]] <= a[i]) dq.pop();
    dq.push(i);
    if (dq[0] <= i - k) dq.shift();
    if (i >= k - 1) res.push(a[dq[0]]);
  }
  return res;
}

A max-heap of (value, index) also works in O(n log k) — pop stale indices lazily.

Kth smallest and largest element in an unsorted arrayMedium1 approach

Problem

Given an unsorted array of distinct values and k, return the kth smallest and the kth largest element.

Example 1

Input:  arr = [7, 10, 4, 3, 20, 15], k = 3
Output: kth smallest 7, kth largest 10

Also asked as: Kth smallest and largest element in an unsorted array · “k” largest element in an array

1. One heap of size k

Time O(n log k)Space O(k)

Kth largest → min-heap of size k (root is the answer). Kth smallest → max-heap of size k. Quickselect gives average O(n).

function kthLargest(a, k) {
  const h = []; // min-heap as sorted array for brevity
  for (const x of a) {
    let i = h.findIndex((v) => v > x);
    i === -1 ? h.push(x) : h.splice(i, 0, x);
    if (h.length > k) h.shift();
  }
  return h[0];
}
const kthSmallest = (a, k) => kthLargest(a, a.length - k + 1);
Merge K sorted arraysMedium1 approach

Problem

Given k sorted arrays, return one sorted array containing all their elements. Aim for O(N log k), where N is the total number of elements.

Example 1

Input:  [[1, 3, 5, 7], [2, 4, 6, 8], [0, 9, 10, 11]]
Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Also asked as: Merge “K” sorted arrays

1. Min-heap of (value, arrayIdx, elemIdx)

Time O(N log K)Space O(K)

Seed with the first element of each array; pop the smallest, output it, push the next element from the same array.

function mergeKArrays(arrays) {
  const heap = arrays.map((arr, i) => [arr[0], i, 0]).filter((x) => x[0] !== undefined);
  heap.sort((a, b) => a[0] - b[0]);
  const out = [];
  while (heap.length) {
    const [val, ai, ei] = heap.shift();
    out.push(val);
    if (ei + 1 < arrays[ai].length) {
      const next = [arrays[ai][ei + 1], ai, ei + 1];
      let i = heap.findIndex((x) => x[0] > next[0]);
      i === -1 ? heap.push(next) : heap.splice(i, 0, next);
    }
  }
  return out;
}
Merge two binary max heapsEasy1 approach

Problem

Given two max-heaps stored as arrays, return a single valid max-heap array containing all their elements.

Example 1

Input:  a = [10, 5, 6, 2], b = [12, 7, 9]
Output: [12, 10, 9, 2, 5, 7, 6] (any valid max-heap)

Also asked as: Merge 2 Binary Max Heaps

1. Concatenate the arrays and re-heapify

Time O(n + m)Space O(1) extra

A heap is just an array; join both backing arrays and build-heap in O(n).

function mergeMaxHeaps(a, b) {
  const arr = a.concat(b), n = arr.length;
  const down = (i) => {
    for (;;) {
      let s = i, l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && arr[l] > arr[s]) s = l;
      if (r < n && arr[r] > arr[s]) s = r;
      if (s === i) break;
      [arr[s], arr[i]] = [arr[i], arr[s]]; i = s;
    }
  };
  for (let i = (n >> 1) - 1; i >= 0; i--) down(i);
  return arr;
}
Kth largest sum of contiguous subarraysMedium1 approach

Problem

Consider the sums of all contiguous subarrays. Return the kth largest of these sums.

Example 1

Input:  arr = [20, -5, -1], k = 3
Output: 14

Sums: 20, 15, 14, −5, −6, −1. The 3rd largest is 14.

Also asked as: Kth largest sum continuous subarrays

1. All prefix sums + min-heap of size k

Time O(n² log k)Space O(k)

Every subarray sum is prefix[j] − prefix[i]. Generate them and keep the k largest in a size-k min-heap.

function kthLargestSubarraySum(a, k) {
  const prefix = [0];
  for (const x of a) prefix.push(prefix[prefix.length - 1] + x);
  const heap = [];
  for (let i = 0; i < a.length; i++)
    for (let j = i + 1; j <= a.length; j++) {
      const s = prefix[j] - prefix[i];
      let p = heap.findIndex((v) => v > s);
      p === -1 ? heap.push(s) : heap.splice(p, 0, s);
      if (heap.length > k) heap.shift();
    }
  return heap[0];
}
Smallest range covering elements from K listsHard1 approach

Problem

Given k sorted lists, find the smallest range [a, b] that includes at least one number from each list. A range is smaller if it is narrower, or equally wide with a smaller a.

Example 1

Input:  [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20, 24]

Also asked as: Smallest range in “K” Lists

1. Min-heap of one element per list, track the running max

Time O(N log K)Space O(K)

Keep one pointer per list in a min-heap; the range is [heapMin, currentMax]. Pop the min, advance that list, update max. Stop when a list is exhausted.

function smallestRange(lists) {
  let heap = lists.map((l, i) => [l[0], i, 0]);
  heap.sort((a, b) => a[0] - b[0]);
  let curMax = Math.max(...heap.map((x) => x[0]));
  let best = [heap[0][0], curMax];
  while (true) {
    const [val, li, ei] = heap.shift();
    if (curMax - val < best[1] - best[0]) best = [val, curMax];
    if (ei + 1 === lists[li].length) break;
    const nxt = [lists[li][ei + 1], li, ei + 1];
    curMax = Math.max(curMax, nxt[0]);
    let p = heap.findIndex((x) => x[0] > nxt[0]);
    p === -1 ? heap.push(nxt) : heap.splice(p, 0, nxt);
  }
  return best;
}
Median in a stream of integersHard1 approach

Problem

Numbers arrive one at a time. After each insertion, report the median of everything seen so far. Insertion should be O(log n) and reading the median O(1).

Example 1

Input:  stream 5, 15, 1, 3
Output: 5, 10, 5, 4

Also asked as: Median in a stream of Integers

1. Two heaps — max-heap for the low half, min-heap for the high half

Time O(log n) per insert, O(1) querySpace O(n)

Keep the halves balanced (sizes differ by ≤ 1). The median is the top of the larger heap, or the average of both tops.

class MedianFinder {
  constructor() { this.low = []; this.high = []; } // low is a max-heap, high a min-heap (sorted arrays here)
  addNum(x) {
    const push = (h, v, cmp) => { let i = h.findIndex((e) => cmp(e, v)); i === -1 ? h.push(v) : h.splice(i, 0, v); };
    push(this.low, x, (e, v) => e < v);            // descending
    this.high.push(this.low.shift());
    this.high.sort((a, b) => a - b);
    if (this.high.length > this.low.length) { this.low.unshift(this.high.shift()); this.low.sort((a, b) => b - a); }
  }
  findMedian() {
    if (this.low.length > this.high.length) return this.low[0];
    return (this.low[0] + this.high[0]) / 2;
  }
}

Use real binary heaps for O(log n); the sorted-array version above is O(n) per insert but shows the idea.

Check whether a binary tree is a heapMedium1 approach

Problem

Return true if the binary tree is a max-heap: it is complete (every level full except possibly the last, which is filled from the left), and every node is at least as large as its children.

Example 1

Input:  [97, 46, 37, 12, 3, 7, 31, 6, 9]
Output: true

Also asked as: Check if a Binary Tree is Heap

1. Complete-tree check + heap-order check

Time O(n)Space O(h)

Count nodes; a node at index i is valid only if i < count (completeness). Separately verify every node ≥ its children (max-heap).

function isHeap(root) {
  const count = (n) => (n ? 1 + count(n.left) + count(n.right) : 0);
  const total = count(root);
  const complete = (n, i) => {
    if (!n) return true;
    if (i >= total) return false;
    return complete(n.left, 2 * i + 1) && complete(n.right, 2 * i + 2);
  };
  const ordered = (n) => {
    if (!n) return true;
    if (n.left && n.left.val > n.val) return false;
    if (n.right && n.right.val > n.val) return false;
    return ordered(n.left) && ordered(n.right);
  };
  return complete(root, 0) && ordered(root);
}
Connect n ropes with minimum costEasy1 approach

Problem

Connecting two ropes of lengths a and b costs a + b and produces a rope of length a + b. Return the minimum total cost to connect all the ropes into one.

Example 1

Input:  [4, 3, 2, 6]
Output: 29

2+3=5, 4+5=9, 6+9=15 → 5 + 9 + 15.

Also asked as: Connect “n” ropes with minimum cost

1. Min-heap greedy (Huffman-style)

Time O(n log n)Space O(n)

Always join the two shortest ropes; add the combined length to the cost and back to the heap.

function connectRopes(lengths) {
  const heap = [...lengths].sort((a, b) => a - b);
  let cost = 0;
  while (heap.length > 1) {
    const a = heap.shift(), b = heap.shift();
    const sum = a + b;
    cost += sum;
    let i = heap.findIndex((v) => v > sum);
    i === -1 ? heap.push(sum) : heap.splice(i, 0, sum);
  }
  return cost;
}
Convert a BST to a min-heapMedium1 approach

Problem

Given a BST that is a complete binary tree, rearrange its values in place so it becomes a min-heap in which every left subtree's values are smaller than every right subtree's values (preorder = sorted order).

Example 1

Input:  BST [4, 2, 6, 1, 3, 5, 7]
Output: [1, 2, 5, 3, 4, 6, 7]

Also asked as: Convert BST to Min Heap

1. In-order values → fill nodes in pre-order

Time O(n)Space O(n)

In-order of a BST is sorted. Traverse the tree in pre-order and assign the sorted values in sequence — every parent then gets a smaller value than its children (a min-heap where the left subtree is entirely smaller than the right).

function bstToMinHeap(root) {
  const vals = [];
  (function inorder(n) { if (n) { inorder(n.left); vals.push(n.val); inorder(n.right); } })(root);
  let i = 0;
  (function preorder(n) { if (n) { n.val = vals[i++]; preorder(n.left); preorder(n.right); } })(root);
  return root;
}
Minimum sum of two numbers formed from digits of an arrayEasy1 approach

Problem

Use every digit in the array exactly once to form two numbers whose sum is as small as possible. Return that sum.

Example 1

Input:  [6, 8, 4, 5, 2, 3]
Output: 604

246 + 358.

Also asked as: Minimum sum of two numbers formed from digits of an array

1. Sort ascending, deal digits alternately to two numbers

Time O(n log n)Space O(n)

Smallest digits belong in the highest place values; alternating them between the two numbers keeps both small and equal in length.

function minSum(digits) {
  digits.sort((a, b) => a - b);
  let n1 = '', n2 = '';
  digits.forEach((d, i) => (i % 2 === 0 ? (n1 += d) : (n2 += d)));
  return (BigInt(n1 || 0) + BigInt(n2 || 0)).toString();
}
Top K Frequent ElementsMedium2 approaches

Problem

Return the k most frequent elements, in any order. The answer is guaranteed to be unique. Aim for better than O(n log n).

Example 1

Input:  nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]

1. Count + sort

Time O(n log n)Space O(n)

Count with a map, sort entries by count descending, take k.

function topKFrequent(nums, k) {
  const cnt = new Map();
  for (const x of nums) cnt.set(x, (cnt.get(x) ?? 0) + 1);
  return [...cnt].sort((a, b) => b[1] - a[1]).slice(0, k).map(([x]) => x);
}

2. Bucket sort by frequency

Time O(n)Space O(n)

A count is between 1 and n, so bucket values by count and read buckets from high to low.

function topKFrequent(nums, k) {
  const cnt = new Map();
  for (const x of nums) cnt.set(x, (cnt.get(x) ?? 0) + 1);
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [x, c] of cnt) buckets[c].push(x);
  const res = [];
  for (let c = nums.length; c > 0 && res.length < k; c--) res.push(...buckets[c]);
  return res.slice(0, k);
}

A min-heap of size k is O(n log k) and is the answer interviewers expect if they forbid bucket sort.

K Closest Points to OriginMedium2 approaches

Problem

Given points [x, y], return the k points closest to the origin by Euclidean distance, in any order.

Example 1

Input:  points = [[3,3], [5,-1], [-2,4]], k = 2
Output: [[3,3], [-2,4]]

1. Sort by distance

Time O(n log n)Space O(n)

Sort by x² + y² (no square root needed) and take k.

const kClosest = (points, k) =>
  points.sort((a, b) => a[0] ** 2 + a[1] ** 2 - (b[0] ** 2 + b[1] ** 2)).slice(0, k);

2. Max-heap of size k

Time O(n log k)Space O(k)

Keep the k closest so far; the root is the farthest of them and gets evicted when a closer point arrives. MinHeap is the class from the patterns page with a reversed comparator.

function kClosest(points, k) {
  const d = ([x, y]) => x * x + y * y;
  const heap = new MinHeap((a, b) => d(b) - d(a)); // max-heap by distance
  for (const p of points) {
    heap.push(p);
    if (heap.size > k) heap.pop();
  }
  return heap.a;
}

Quickselect gives O(n) average if asked for better than n log k.

Last Stone WeightEasy1 approach

Problem

Each turn, smash the two heaviest stones, x ≤ y. If x == y both are destroyed; otherwise a stone of weight y − x remains. Return the weight of the last stone, or 0 if none is left.

Example 1

Input:  [2, 7, 4, 1, 8, 1]
Output: 1

1. Max-heap simulation

Time O(n log n)Space O(n)

Repeatedly smash the two heaviest; push back the difference if non-zero.

function lastStoneWeight(stones) {
  const heap = new MinHeap((a, b) => b - a);
  stones.forEach((s) => heap.push(s));
  while (heap.size > 1) {
    const y = heap.pop(), x = heap.pop();
    if (y !== x) heap.push(y - x);
  }
  return heap.size ? heap.peek() : 0;
}
Task SchedulerMedium1 approach

Problem

Tasks are letters, and each takes one unit of time. Two runs of the same task must be at least n units apart; the CPU can idle in between. Return the minimum total time to finish all tasks.

Example 1

Input:  tasks = ["A","A","A","B","B","B"], n = 2
Output: 8

A B idle A B idle A B.

Example 2

Input:  same tasks, n = 0
Output: 6

1. Counting formula

Time O(n)Space O(26)

The most frequent task (count f) forces (f − 1) blocks of length n + 1, plus one slot for each task tied at count f. If tasks outnumber that, no idle is needed.

function leastInterval(tasks, n) {
  const cnt = new Array(26).fill(0);
  for (const t of tasks) cnt[t.charCodeAt(0) - 65]++;
  const f = Math.max(...cnt);
  const tied = cnt.filter((c) => c === f).length;
  return Math.max(tasks.length, (f - 1) * (n + 1) + tied);
}

The simulation (max-heap of counts + cooldown queue) is O(total time) and easier to derive live — present it if the formula does not come to you.