Top K elements interview questions with worked solutions
Last updated 2026-11-19
Top-K problems ask for the k largest, smallest, most frequent or closest items. Sorting everything costs O(n log n), but a heap of size k reduces that to O(n log k), and for streams it is the only approach that keeps memory bounded. Counting frequencies first and using buckets can bring some variants down to O(n).
The rule of thumb is a surprise to many people: to keep the k largest items use a min-heap of size k, because the root is the smallest of the survivors and is the one to evict. To keep the k smallest use a max-heap. The ten problems below apply that idea to numbers, frequencies, points, strings, merged lists and a running median. Related pages are sorting algorithms questions for quickselect and queue and deque questions.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Core idea | Heap of size k, O(n log k) |
Heap cheat sheet
Python heapq is a min-heap; push negative values (or tuples with negated keys) for a max-heap. Java PriorityQueue is also a min-heap by default; pass Collections.reverseOrder() or a comparator for a max-heap. Push and pop cost O(log n); peeking at the root is O(1); building a heap from n items is O(n).
With a heap of size k, process each element once: push, and if the size exceeds k, pop the root. Total cost is O(n log k) time and O(k) space.
- k largest: min-heap of size k.
- k smallest or closest: max-heap of size k.
- k most frequent: count, then heap or bucket by frequency.
- Running median: max-heap for the lower half and min-heap for the upper half.
Alternatives and trade-offs
Quickselect finds the kth element in O(n) average time but modifies the array and does not suit streams. Sorting is simplest and fine for small inputs. A heap is the right answer for streams and for k much smaller than n. Mention all three and justify your choice.
Top K elements interview questions with worked solutions: questions with worked answers
1 Kth largest element in a stream: add numbers and report the kth largest after each add.
easyKeep a min-heap holding exactly the k largest numbers seen so far. When a new number arrives, push it, and if the heap has more than k items, pop the smallest. The root is then the kth largest. Initialise by adding the starting numbers one at a time. Time O(log k) per add, space O(k).. Edge cases: fewer than k numbers initially (the root is not yet defined until k are added), duplicates, negative values.
pythonimport heapq class KthLargest: def __init__(self, k, nums): self.k = k self.heap = [] for x in nums: self.add(x) def add(self, val): heapq.heappush(self.heap, val) if len(self.heap) > self.k: heapq.heappop(self.heap) return self.heap[0]javaimport java.util.*; class KthLargest { private final int k; private final PriorityQueue<Integer> heap = new PriorityQueue<>(); KthLargest(int k, int[] nums) { this.k = k; for (int x : nums) add(x); } int add(int val) { heap.add(val); if (heap.size() > k) heap.poll(); return heap.peek(); } }2 Kth largest element in an unsorted array.
mediumUse a min-heap of size k. Push each element; when the size exceeds k pop the smallest. After all elements, the root is the kth largest. For [3,2,1,5,6,4] and k = 2 the heap ends as [5,6] with root 5. Quickselect gives O(n) average time at the cost of modifying the array. Time O(n log k), space O(k).. Edge cases: k = 1 (the maximum), k = n (the minimum), duplicates (counted separately).
pythonimport heapq def find_kth_largest(a, k): heap = [] for x in a: heapq.heappush(heap, x) if len(heap) > k: heapq.heappop(heap) return heap[0]javaimport java.util.*; class Solution { static int findKthLargest(int[] a, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(); for (int x : a) { heap.add(x); if (heap.size() > k) heap.poll(); } return heap.peek(); } }3 Top K frequent elements.
mediumCount occurrences with a map. A heap of size k over the counts gives O(n log k). A bucket approach gives O(n): make buckets indexed by frequency (the maximum frequency is at most n), place each value in its bucket, then read buckets from the highest frequency down until you have k values. Time O(n), space O(n).. Edge cases: k equal to the number of distinct values, all values equal, ties (any order is usually accepted).
pythonfrom collections import Counter def top_k_frequent(nums, k): cnt = Counter(nums) buckets = [[] for _ in range(len(nums) + 1)] for v, c in cnt.items(): buckets[c].append(v) res = [] for c in range(len(nums), 0, -1): for v in buckets[c]: res.append(v) if len(res) == k: return res return resjavaimport java.util.*; class Solution { static int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> cnt = new HashMap<>(); for (int x : nums) cnt.merge(x, 1, Integer::sum); List<Integer>[] buckets = new List[nums.length + 1]; for (var e : cnt.entrySet()) { if (buckets[e.getValue()] == null) buckets[e.getValue()] = new ArrayList<>(); buckets[e.getValue()].add(e.getKey()); } int[] res = new int[k]; int idx = 0; for (int c = nums.length; c > 0 && idx < k; c--) { if (buckets[c] == null) continue; for (int v : buckets[c]) { if (idx == k) break; res[idx++] = v; } } return res; } }4 K closest points to the origin.
mediumCompare squared distances x^2 + y^2, which avoids square roots and keeps the order. Keep a max-heap of size k keyed by distance: push each point, and when the size exceeds k pop the farthest. The heap then holds the k closest points. Time O(n log k), space O(k).. Edge cases: k equal to the number of points, ties in distance, points at the origin.
pythonimport heapq def k_closest(points, k): heap = [] for x, y in points: heapq.heappush(heap, (-(x * x + y * y), x, y)) if len(heap) > k: heapq.heappop(heap) return [[x, y] for _, x, y in heap]javaimport java.util.*; class Solution { static int[][] kClosest(int[][] points, int k) { PriorityQueue<int[]> heap = new PriorityQueue<>( (a, b) -> Integer.compare(b[0] * b[0] + b[1] * b[1], a[0] * a[0] + a[1] * a[1])); for (int[] p : points) { heap.add(p); if (heap.size() > k) heap.poll(); } return heap.toArray(new int[0][]); } }5 Connect ropes: the minimum total cost to join all ropes when joining two costs the sum of their lengths.
easyAlways join the two shortest ropes, because every join adds its cost again to every later join that contains it, so small ropes should be merged first. Use a min-heap: pop two, add their sum to the total cost, push the sum back, repeat until one rope remains. This is Huffman coding in disguise. Time O(n log n), space O(n).. Edge cases: one rope (cost 0), two ropes, many equal lengths.
pythonimport heapq def connect_ropes(ropes): heapq.heapify(ropes) total = 0 while len(ropes) > 1: s = heapq.heappop(ropes) + heapq.heappop(ropes) total += s heapq.heappush(ropes, s) return totaljavaimport java.util.*; class Solution { static long connectRopes(int[] ropes) { PriorityQueue<Long> heap = new PriorityQueue<>(); for (int r : ropes) heap.add((long) r); long total = 0; while (heap.size() > 1) { long s = heap.poll() + heap.poll(); total += s; heap.add(s); } return total; } }6 Reorganise a string so no two adjacent characters are equal, or return an empty string if impossible.
mediumIf any character appears more than (n + 1) / 2 times, it is impossible. Otherwise always place the most frequent remaining character that differs from the previous one. Keep a max-heap of counts; pop the top, append it, hold it back for one round, and push the previous held character back if it still has copies. Time O(n log 26), effectively O(n); space O(1).. Edge cases: a character with more than half the letters (empty result), a single character, all characters distinct.
pythonimport heapq from collections import Counter def reorganize_string(s): cnt = Counter(s) if max(cnt.values()) > (len(s) + 1) // 2: return "" heap = [(-c, ch) for ch, c in cnt.items()] heapq.heapify(heap) res, prev = [], (0, '') while heap: c, ch = heapq.heappop(heap) res.append(ch) if prev[0] < 0: heapq.heappush(heap, prev) prev = (c + 1, ch) return "".join(res)javaimport java.util.*; class Solution { static String reorganizeString(String s) { int[] cnt = new int[26]; for (char ch : s.toCharArray()) cnt[ch - 'a']++; int max = 0; for (int c : cnt) max = Math.max(max, c); if (max > (s.length() + 1) / 2) return ""; PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]); for (int i = 0; i < 26; i++) if (cnt[i] > 0) heap.add(new int[]{cnt[i], i}); StringBuilder sb = new StringBuilder(); int[] prev = null; while (!heap.isEmpty()) { int[] cur = heap.poll(); sb.append((char) ('a' + cur[1])); if (prev != null && prev[0] > 0) heap.add(prev); cur[0]--; prev = cur; } return sb.toString(); } }7 Top K frequent words, with ties broken alphabetically.
mediumCount the words, then pick the k best by the key (-count, word), so higher counts come first and equal counts come in alphabetical order. heapq.nsmallest with that key does it in O(n log k). In Java, keep a min-heap ordered by count ascending and word descending, evict when it exceeds k, then reverse the result. Time O(n log k), space O(n).. Edge cases: ties across several words, k equal to the number of distinct words, case sensitivity.
pythonimport heapq from collections import Counter def top_k_frequent_words(words, k): cnt = Counter(words) return heapq.nsmallest(k, cnt, key=lambda w: (-cnt[w], w))javaimport java.util.*; class Solution { static List<String> topKFrequentWords(String[] words, int k) { Map<String, Integer> cnt = new HashMap<>(); for (String w : words) cnt.merge(w, 1, Integer::sum); PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> cnt.get(a).equals(cnt.get(b)) ? b.compareTo(a) : cnt.get(a) - cnt.get(b)); for (String w : cnt.keySet()) { heap.add(w); if (heap.size() > k) heap.poll(); } LinkedList<String> res = new LinkedList<>(); while (!heap.isEmpty()) res.addFirst(heap.poll()); return res; } }8 Find the k closest elements to x in a sorted array.
mediumThe answer is a contiguous window of length k. Binary search for the left edge of that window over the range 0 to n - k: compare x - a[mid] with a[mid + k] - x. If the left element is farther from x, the window must move right; otherwise it can stay or move left. This avoids a heap and runs in O(log(n - k) + k). Time O(log(n - k) + k), space O(1) beyond the output.. Edge cases: x smaller or larger than every element, ties (prefer the smaller value, hence the strict comparison), k equal to the length.
pythondef find_closest_elements(a, k, x): lo, hi = 0, len(a) - k while lo < hi: mid = (lo + hi) // 2 if x - a[mid] > a[mid + k] - x: lo = mid + 1 else: hi = mid return a[lo:lo + k]javaimport java.util.*; class Solution { static List<Integer> findClosestElements(int[] a, int k, int x) { int lo = 0, hi = a.length - k; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (x - a[mid] > a[mid + k] - x) lo = mid + 1; else hi = mid; } List<Integer> res = new ArrayList<>(); for (int i = lo; i < lo + k; i++) res.add(a[i]); return res; } }9 Find K pairs with the smallest sums from two sorted arrays.
hardThink of a grid of sums nums1[i] + nums2[j] where rows and columns are sorted. Start a min-heap with the pairs (i, 0) for the first k values of nums1. Pop the smallest pair (i, j), record it, and push (i, j + 1) if it exists. Each pop reveals the next smallest, so after k pops you have the answer without forming all n * m pairs. Time O(k log k), space O(k).. Edge cases: k larger than n * m (return all pairs), duplicate values, one array of length 1.
pythonimport heapq def k_smallest_pairs(a, b, k): if not a or not b: return [] heap = [(a[i] + b[0], i, 0) for i in range(min(k, len(a)))] heapq.heapify(heap) res = [] while heap and len(res) < k: _, i, j = heapq.heappop(heap) res.append([a[i], b[j]]) if j + 1 < len(b): heapq.heappush(heap, (a[i] + b[j + 1], i, j + 1)) return resjavaimport java.util.*; class Solution { static List<List<Integer>> kSmallestPairs(int[] a, int[] b, int k) { List<List<Integer>> res = new ArrayList<>(); if (a.length == 0 || b.length == 0) return res; PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> Integer.compare(a[x[0]] + b[x[1]], a[y[0]] + b[y[1]])); for (int i = 0; i < Math.min(k, a.length); i++) heap.add(new int[]{i, 0}); while (!heap.isEmpty() && res.size() < k) { int[] cur = heap.poll(); res.add(Arrays.asList(a[cur[0]], b[cur[1]])); if (cur[1] + 1 < b.length) heap.add(new int[]{cur[0], cur[1] + 1}); } return res; } }10 Find the median from a data stream.
hardSplit the numbers into a lower half in a max-heap and an upper half in a min-heap, keeping their sizes equal or the lower half one larger. For each new number, push it to the lower heap, move the lower heap maximum to the upper heap, and if the upper heap becomes larger, move its minimum back. The median is the root of the lower heap, or the average of both roots when the sizes are equal. Time O(log n) per insert, O(1) per median; space O(n).. Edge cases: a single number, even and odd counts, duplicate values, a median query with no data (undefined).
pythonimport heapq class MedianFinder: def __init__(self): self.small = [] self.large = [] def add_num(self, x): heapq.heappush(self.small, -x) heapq.heappush(self.large, -heapq.heappop(self.small)) if len(self.large) > len(self.small): heapq.heappush(self.small, -heapq.heappop(self.large)) def find_median(self): if len(self.small) > len(self.large): return float(-self.small[0]) return (-self.small[0] + self.large[0]) / 2javaimport java.util.*; class MedianFinder { private final PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder()); private final PriorityQueue<Integer> large = new PriorityQueue<>(); void addNum(int x) { small.add(x); large.add(small.poll()); if (large.size() > small.size()) small.add(large.poll()); } double findMedian() { if (small.size() > large.size()) return small.peek(); return ((long) small.peek() + large.peek()) / 2.0; } }
Frequently asked questions
Why use a min-heap to keep the k largest?
The root of a min-heap is the smallest of the k survivors, which is exactly the element that must be evicted when a larger one arrives. A max-heap would put the wrong element at the root.
Heap or sort for top-k?
Sorting is O(n log n) and simplest. A heap of size k is O(n log k) and works on streams. Quickselect averages O(n) but modifies the array. Say which fits the constraints.
How do I build a max-heap in Python?
heapq only provides a min-heap, so push negated values or tuples with a negated key, and negate again when reading.
What is the cost of building a heap from n items?
O(n) with heapify, but pushing items one at a time is O(n log n). For top-k with a size-k heap, use the push-and-pop loop.
Which other problems use heaps?
Merging k sorted lists, scheduling and Dijkstra. See linked list questions for k-way merge and intervals questions for heap-based scheduling.
Related guides
- Sorting algorithm interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Linked list interview questions with worked solutions
- Interval interview questions with worked solutions
- Hashing interview questions with worked solutions
- Greedy algorithm interview questions with worked solutions
More in DSA Interview Questions
- Topological Sort Interview Questions
- Tree DP Interview Questions
- Tree Traversal Interview Questions
- Trie (Prefix Tree) Interview Questions
- Two pointers interview questions with worked solutions
- Union-Find (Disjoint Set Union) Interview Questions
- Array interview questions with worked solutions
- Backtracking interview questions with worked solutions
- BFS (Breadth-First Search) Interview Questions
- Binary search interview questions with worked solutions
- Binary Search Tree Interview Questions and Answers
- Binary Tree Interview Questions and Answers