Autocoder

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.

Problems10, easy to hard
LanguagesPython and Java
Core ideaHeap 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.

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. 1

    Kth largest element in a stream: add numbers and report the kth largest after each add.

    easy

    Keep 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.

    python
    import 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]
    java
    import 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. 2

    Kth largest element in an unsorted array.

    medium

    Use 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).

    python
    import 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]
    java
    import 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. 3

    Top K frequent elements.

    medium

    Count 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).

    python
    from 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 res
    java
    import 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. 4

    K closest points to the origin.

    medium

    Compare 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.

    python
    import 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]
    java
    import 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. 5

    Connect ropes: the minimum total cost to join all ropes when joining two costs the sum of their lengths.

    easy

    Always 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.

    python
    import 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 total
    java
    import 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. 6

    Reorganise a string so no two adjacent characters are equal, or return an empty string if impossible.

    medium

    If 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.

    python
    import 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)
    java
    import 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. 7

    Top K frequent words, with ties broken alphabetically.

    medium

    Count 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.

    python
    import 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))
    java
    import 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. 8

    Find the k closest elements to x in a sorted array.

    medium

    The 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.

    python
    def 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]
    java
    import 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. 9

    Find K pairs with the smallest sums from two sorted arrays.

    hard

    Think 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.

    python
    import 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 res
    java
    import 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. 10

    Find the median from a data stream.

    hard

    Split 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).

    python
    import 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]) / 2
    java
    import 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

More in DSA Interview Questions

See all in this section