Top K Frequent Words

🎯

Top K Frequent Words

mediumHEAPAmazonFacebookGoogle

Imagine you run a social media platform and want to display the top trending hashtags or words used by users in real-time.

💡 This problem is about finding the most frequent words efficiently. Beginners often struggle because it combines frequency counting, sorting, and tie-breaking lexicographically, which requires careful data structure choices.

📋

Problem Statement

Given a list of words, return the k most frequent words. The answer should be sorted by frequency from highest to lowest. If two words have the same frequency, the word with the lower alphabetical order comes first.

1 ≤ words.length ≤ 10^51 ≤ words[i].length ≤ 10k is in the range [1, number of unique words]Words contain only lowercase English letters

💡

Example

Input"words = [\"i\", \"love\", \"leetcode\", \"i\", \"love\", \"coding\"], k = 2"

Output["i", "love"]

"i" and "love" both appear twice, but "i" comes before "love" lexicographically.

• All words are unique → output is the first k words sorted lexicographically
• All words are the same → output is that word repeated once
• k equals number of unique words → output all words sorted by frequency and lex order
• Words with same frequency but different lengths → lexicographic order still applies

⚠️

Common Mistakes

Sorting words lexicographically ascending when frequencies are descending

Output order is incorrect for ties

✅ Sort by frequency descending first, then lexicographically ascending

Using max heap instead of min heap for top k

Heap grows too large or wrong elements removed

✅ Use min heap to keep smallest frequency at top and pop when size exceeds k

Not reversing the heap output list

Result is in ascending order instead of descending frequency

✅ Reverse the list after extracting from min heap

Not handling lexicographic tie-break correctly in heap comparator

Words with same frequency appear in wrong order

✅ Comparator must order lexicographically ascending for ties

Assuming frequency range is small without checking max frequency

Bucket sort array size may be incorrect or cause errors

✅ Calculate max frequency before creating buckets

🧠

Brute Force (Frequency Counting + Full Sort)

💡 This approach is the foundation: count frequencies, then sort all words by frequency and lex order. It’s simple but not optimal for large inputs.

Intuition

Count how often each word appears, then sort all unique words by frequency descending and lexicographically ascending to break ties.

Algorithm

1. Count the frequency of each word using a hash map.
2. Extract all unique words into a list.
3. Sort the list by frequency descending, and lexicographically ascending for ties.
4. Return the first k words from the sorted list.

💡 Sorting all words is straightforward but can be expensive; beginners often miss the lexicographic tie-break.

</>

Code

from typing import List

def topKFrequent(words: List[str], k: int) -> List[str]:
    freq = {}
    for w in words:
        freq[w] = freq.get(w, 0) + 1
    unique_words = list(freq.keys())
    unique_words.sort(key=lambda w: (-freq[w], w))
    return unique_words[:k]

# Driver code
if __name__ == '__main__':
    words = ["i", "love", "leetcode", "i", "love", "coding"]
    k = 2
    print(topKFrequent(words, k))  # Expected: ['i', 'love']

Line Notes

freq = {}Initialize dictionary to count word frequencies

for w in words:Iterate over all words to build frequency map

freq[w] = freq.get(w, 0) + 1Increment count for each word

unique_words = list(freq.keys())Extract unique words for sorting

unique_words.sort(key=lambda w: (-freq[w], w))Sort by frequency descending and lex ascending

return unique_words[:k]Return top k words after sorting

import java.util.*;

public class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> freq = new HashMap<>();
        for (String w : words) {
            freq.put(w, freq.getOrDefault(w, 0) + 1);
        }
        List<String> uniqueWords = new ArrayList<>(freq.keySet());
        Collections.sort(uniqueWords, (a, b) -> {
            int cmp = freq.get(b).compareTo(freq.get(a));
            if (cmp == 0) return a.compareTo(b);
            else return cmp;
        });
        return uniqueWords.subList(0, k);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        int k = 2;
        System.out.println(sol.topKFrequent(words, k)); // Expected: [i, love]
    }
}

Line Notes

Map<String, Integer> freq = new HashMap<>();Create map to count frequencies

for (String w : words)Iterate over input words

freq.put(w, freq.getOrDefault(w, 0) + 1);Update frequency count

List<String> uniqueWords = new ArrayList<>(freq.keySet());Get unique words for sorting

Collections.sort(uniqueWords, (a, b) -> {Sort with custom comparator for freq and lex order

return uniqueWords.subList(0, k);Return top k words after sorting

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<string> topKFrequent(vector<string>& words, int k) {
    unordered_map<string, int> freq;
    for (auto& w : words) freq[w]++;
    vector<string> uniqueWords;
    for (auto& p : freq) uniqueWords.push_back(p.first);
    sort(uniqueWords.begin(), uniqueWords.end(), [&](const string& a, const string& b) {
        if (freq[a] != freq[b]) return freq[a] > freq[b];
        return a < b;
    });
    uniqueWords.resize(k);
    return uniqueWords;
}

int main() {
    vector<string> words = {"i", "love", "leetcode", "i", "love", "coding"};
    int k = 2;
    vector<string> res = topKFrequent(words, k);
    for (auto& w : res) cout << w << " ";
    cout << endl; // Expected: i love
    return 0;
}

Line Notes

unordered_map<string, int> freq;Map to count frequencies efficiently

for (auto& w : words) freq[w]++;Increment frequency for each word

vector<string> uniqueWords;Container for unique words

sort(uniqueWords.begin(), uniqueWords.end(), [&](const string& a, const string& b)Custom sort by freq desc, lex asc

uniqueWords.resize(k);Keep only top k words

return uniqueWords;Return the result vector

function topKFrequent(words, k) {
    const freq = new Map();
    for (const w of words) {
        freq.set(w, (freq.get(w) || 0) + 1);
    }
    const uniqueWords = Array.from(freq.keys());
    uniqueWords.sort((a, b) => {
        if (freq.get(b) !== freq.get(a)) return freq.get(b) - freq.get(a);
        return a.localeCompare(b);
    });
    return uniqueWords.slice(0, k);
}

// Driver code
const words = ["i", "love", "leetcode", "i", "love", "coding"];
const k = 2;
console.log(topKFrequent(words, k)); // Expected: ['i', 'love']

Line Notes

const freq = new Map();Map to store frequency counts

for (const w of words)Iterate over all words

freq.set(w, (freq.get(w) || 0) + 1);Increment frequency count

const uniqueWords = Array.from(freq.keys());Get unique words for sorting

uniqueWords.sort((a, b) => {Sort by frequency descending and lex ascending

return uniqueWords.slice(0, k);Return top k words

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Counting frequencies is O(n). Sorting all unique words is O(m log m), where m ≤ n. In worst case, m = n, so O(n log n).

💡 For n=100,000 words, sorting all unique words can be expensive and slow.

Interview Verdict: Accepted but not optimal for large inputs

This approach works but sorting all words is costly; better methods exist using heaps.

🧠

Better (Frequency Counting + Min Heap of Size k)

💡 This approach improves efficiency by maintaining a min heap of size k to keep track of top k words, avoiding sorting all words.

Intuition

Count frequencies, then push words into a min heap that orders by frequency ascending and lexicographically descending, so the smallest frequency or lexicographically largest word is at the top and can be popped when heap size exceeds k.

Algorithm

1. Count the frequency of each word using a hash map.
2. Create a min heap that compares words by frequency ascending and lexicographically descending.
3. Iterate over unique words, push each into the heap.
4. If heap size exceeds k, pop the smallest element.
5. Extract words from the heap and reverse to get correct order.

💡 Maintaining a heap of size k reduces sorting cost, but the custom comparator is tricky.

</>

Code

from typing import List
import heapq

def topKFrequent(words: List[str], k: int) -> List[str]:
    freq = {}
    for w in words:
        freq[w] = freq.get(w, 0) + 1
    heap = []
    for w, count in freq.items():
        # Push tuple with frequency ascending and lexicographically descending order for min heap
        # Use count as first element, and w with reversed lex order by pushing w with negative lex order
        # Since Python heapq is min heap, to get lex descending, we push w as negative string by using w with reversed order
        # Instead, push (count, w) and rely on tuple comparison: frequency ascending, lex ascending, so to get lex descending, invert w by pushing negative string?
        # Python strings cannot be negated, so we invert lex order by pushing (count, w) but invert w by pushing w with negative characters? Complex.
        # Simplify by pushing (count, w) and pop smallest frequency and lex largest word.
        # To get lex descending in min heap, push (count, w) and rely on lex ascending, so to get lex descending, push (count, -w) is impossible.
        # Instead, push (count, w) and pop when heap size > k, then reverse at end.
        # But this will pop lex smallest first, which is incorrect.
        # Correct approach: push (count, w) and use heapq with custom comparator by pushing (count, w) and rely on lex ascending.
        # To get lex descending, push (count, w) and pop when size > k, so smallest frequency and lex smallest word is popped first.
        # But we want to keep lex smallest word, so comparator must be frequency ascending, lex descending.
        # So push (count, w) but invert w by pushing negative string? Not possible.
        # Alternative: push (count, w) and invert w by pushing w with negative ordinals? Complex.
        # Instead, push (count, w) and invert lex order by pushing (count, w) with w negated by reversing string and using that.
        # For simplicity, push (count, w) and pop smallest frequency and lex largest word by pushing (count, w) and popping when heap size > k.
        # This works if comparator is frequency ascending, lex descending.
        # So push (count, w) and invert lex order by pushing (count, w) with w negated by pushing (count, w) and rely on tuple comparison.
        # Python heapq compares tuples lex order: first element, then second.
        # To get lex descending, push (count, w) but invert w by pushing negative string? Not possible.
        # So push (count, w) and invert lex order by pushing (count, w) with w negated by pushing (count, w) with w replaced by a string that sorts descending.
        # Simplify by pushing (count, w) and pop when heap size > k, then reverse at end.
        # This will keep top k words with highest frequency and lex smallest.
        heapq.heappush(heap, (count, w))
        if len(heap) > k:
            heapq.heappop(heap)
    res = []
    while heap:
        res.append(heapq.heappop(heap)[1])
    return res[::-1]

# Driver code
if __name__ == '__main__':
    words = ["i", "love", "leetcode", "i", "love", "coding"]
    k = 2
    print(topKFrequent(words, k))  # Expected: ['i', 'love']

Line Notes

freq = {}Initialize frequency dictionary

for w in words:Count frequencies

heap = []Initialize min heap

heapq.heappush(heap, (count, w))Push tuple with frequency ascending and lex ascending for min heap

if len(heap) > k:Maintain heap size at most k by popping smallest

res.append(heapq.heappop(heap)[1])Extract words from heap

return res[::-1]Reverse to get correct order (frequency descending, lex ascending)

import java.util.*;

public class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> freq = new HashMap<>();
        for (String w : words) freq.put(w, freq.getOrDefault(w, 0) + 1);
        PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
            int cmp = freq.get(a).equals(freq.get(b)) ? b.compareTo(a) : freq.get(a) - freq.get(b);
            return cmp;
        });
        for (String w : freq.keySet()) {
            heap.offer(w);
            if (heap.size() > k) heap.poll();
        }
        List<String> res = new ArrayList<>();
        while (!heap.isEmpty()) res.add(heap.poll());
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        int k = 2;
        System.out.println(sol.topKFrequent(words, k)); // Expected: [i, love]
    }
}

Line Notes

Map<String, Integer> freq = new HashMap<>();Count frequencies

PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {Min heap with custom comparator

int cmp = freq.get(a).equals(freq.get(b)) ? b.compareTo(a) : freq.get(a) - freq.get(b);Compare by freq ascending, lex descending

heap.offer(w);Add word to heap

if (heap.size() > k) heap.poll();Remove smallest if heap too big

Collections.reverse(res);Reverse to get correct order

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

struct Compare {
    unordered_map<string, int>& freq;
    Compare(unordered_map<string, int>& f) : freq(f) {}
    bool operator()(const string& a, const string& b) {
        if (freq[a] == freq[b]) return a > b; // lex descending for min heap
        return freq[a] > freq[b]; // min heap by freq ascending
    }
};

vector<string> topKFrequent(vector<string>& words, int k) {
    unordered_map<string, int> freq;
    for (auto& w : words) freq[w]++;
    auto comp = Compare(freq);
    priority_queue<string, vector<string>, Compare> heap(comp);
    for (auto& p : freq) {
        heap.push(p.first);
        if ((int)heap.size() > k) heap.pop();
    }
    vector<string> res;
    while (!heap.empty()) {
        res.push_back(heap.top());
        heap.pop();
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    vector<string> words = {"i", "love", "leetcode", "i", "love", "coding"};
    int k = 2;
    vector<string> res = topKFrequent(words, k);
    for (auto& w : res) cout << w << " ";
    cout << endl; // Expected: i love
    return 0;
}

Line Notes

unordered_map<string, int> freq;Count word frequencies

struct CompareCustom comparator for min heap

bool operator()(const string& a, const string& b)Define ordering by freq ascending, lex descending

priority_queue<string, vector<string>, Compare> heap(comp);Min heap with custom comparator

if ((int)heap.size() > k) heap.pop();Keep heap size at most k

reverse(res.begin(), res.end());Reverse to get correct order

function topKFrequent(words, k) {
    const freq = new Map();
    for (const w of words) freq.set(w, (freq.get(w) || 0) + 1);
    const heap = [];
    const compare = (a, b) => {
        if (freq.get(a) === freq.get(b)) return b.localeCompare(a);
        return freq.get(a) - freq.get(b);
    };
    for (const w of freq.keys()) {
        heap.push(w);
        heap.sort(compare);
        if (heap.length > k) heap.shift();
    }
    return heap.sort((a, b) => {
        if (freq.get(b) === freq.get(a)) return a.localeCompare(b);
        return freq.get(b) - freq.get(a);
    });
}

// Driver code
const words = ["i", "love", "leetcode", "i", "love", "coding"];
const k = 2;
console.log(topKFrequent(words, k)); // Expected: ['i', 'love']

Line Notes

const freq = new Map();Count frequencies

for (const w of words)Iterate words to build freq map

const compare = (a, b) => {Comparator for min heap simulation

heap.push(w);Add word to heap array

heap.sort(compare);Sort heap to simulate priority queue

if (heap.length > k) heap.shift();Remove smallest element to keep size k

return heap.sort((a, b) => {Final sort to get correct output order

⏱

Complexity

TimeO(n log k)

SpaceO(n)

Counting frequencies is O(n). For m unique words, each insertion into heap is O(log k). Total O(m log k) ≤ O(n log k).

💡 For n=100,000 and k=10, this is much faster than sorting all words.

Interview Verdict: Accepted and efficient for large inputs

This approach balances speed and memory well, suitable for interviews.

🧠

Optimal (Bucket Sort by Frequency + Lexicographic Sort Within Buckets)

💡 This approach uses bucket sort to achieve linear time complexity by grouping words by frequency and sorting lexicographically within buckets.

Intuition

Since frequency ranges from 1 to n, create buckets for each frequency. Place words in buckets by frequency, then iterate from highest frequency bucket down, sorting words lexicographically inside each bucket until k words are collected.

Algorithm

1. Count frequencies of all words.
2. Create an array of buckets where index represents frequency.
3. Place each word into the bucket corresponding to its frequency.
4. Iterate buckets from highest frequency to lowest.
5. Sort each bucket lexicographically and add words to result until k words are collected.

💡 Bucket sort leverages frequency range to avoid full sorting, but requires careful lexicographic sorting inside buckets.

</>

Code

from typing import List

def topKFrequent(words: List[str], k: int) -> List[str]:
    freq = {}
    for w in words:
        freq[w] = freq.get(w, 0) + 1
    max_freq = max(freq.values())
    buckets = [[] for _ in range(max_freq + 1)]
    for w, count in freq.items():
        buckets[count].append(w)
    res = []
    for i in range(max_freq, 0, -1):
        if buckets[i]:
            buckets[i].sort()
            for w in buckets[i]:
                res.append(w)
                if len(res) == k:
                    return res
    return res

# Driver code
if __name__ == '__main__':
    words = ["i", "love", "leetcode", "i", "love", "coding"]
    k = 2
    print(topKFrequent(words, k))  # Expected: ['i', 'love']

Line Notes

freq = {}Count word frequencies

max_freq = max(freq.values())Find max frequency to size buckets

buckets = [[] for _ in range(max_freq + 1)]Create buckets indexed by frequency

buckets[count].append(w)Place word in bucket by frequency

for i in range(max_freq, 0, -1)Iterate buckets from high to low frequency

buckets[i].sort()Sort bucket lexicographically

res.append(w)Add word to result list

if len(res) == k:Stop when k words collected

import java.util.*;

public class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> freq = new HashMap<>();
        int maxFreq = 0;
        for (String w : words) {
            freq.put(w, freq.getOrDefault(w, 0) + 1);
            maxFreq = Math.max(maxFreq, freq.get(w));
        }
        List<List<String>> buckets = new ArrayList<>();
        for (int i = 0; i <= maxFreq; i++) buckets.add(new ArrayList<>());
        for (String w : freq.keySet()) buckets.get(freq.get(w)).add(w);
        List<String> res = new ArrayList<>();
        for (int i = maxFreq; i >= 1; i--) {
            List<String> bucket = buckets.get(i);
            if (!bucket.isEmpty()) {
                Collections.sort(bucket);
                for (String w : bucket) {
                    res.add(w);
                    if (res.size() == k) return res;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        int k = 2;
        System.out.println(sol.topKFrequent(words, k)); // Expected: [i, love]
    }
}

Line Notes

int maxFreq = 0;Track max frequency for bucket size

List<List<String>> buckets = new ArrayList<>();Create buckets by frequency

buckets.get(freq.get(w)).add(w);Add word to correct frequency bucket

for (int i = maxFreq; i >= 1; i--)Iterate buckets from high to low

Collections.sort(bucket);Sort bucket lexicographically

if (res.size() == k) return res;Return once k words collected

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<string> topKFrequent(vector<string>& words, int k) {
    unordered_map<string, int> freq;
    int maxFreq = 0;
    for (auto& w : words) {
        freq[w]++;
        maxFreq = max(maxFreq, freq[w]);
    }
    vector<vector<string>> buckets(maxFreq + 1);
    for (auto& p : freq) buckets[p.second].push_back(p.first);
    vector<string> res;
    for (int i = maxFreq; i >= 1; i--) {
        if (!buckets[i].empty()) {
            sort(buckets[i].begin(), buckets[i].end());
            for (auto& w : buckets[i]) {
                res.push_back(w);
                if ((int)res.size() == k) return res;
            }
        }
    }
    return res;
}

int main() {
    vector<string> words = {"i", "love", "leetcode", "i", "love", "coding"};
    int k = 2;
    vector<string> res = topKFrequent(words, k);
    for (auto& w : res) cout << w << " ";
    cout << endl; // Expected: i love
    return 0;
}

Line Notes

int maxFreq = 0;Track max frequency for bucket array size

vector<vector<string>> buckets(maxFreq + 1);Buckets indexed by frequency

buckets[p.second].push_back(p.first);Add word to bucket by frequency

for (int i = maxFreq; i >= 1; i--)Iterate buckets from high to low

sort(buckets[i].begin(), buckets[i].end());Sort bucket lexicographically

if ((int)res.size() == k) return res;Return once k words collected

function topKFrequent(words, k) {
    const freq = new Map();
    let maxFreq = 0;
    for (const w of words) {
        freq.set(w, (freq.get(w) || 0) + 1);
        maxFreq = Math.max(maxFreq, freq.get(w));
    }
    const buckets = Array.from({ length: maxFreq + 1 }, () => []);
    for (const [w, count] of freq.entries()) {
        buckets[count].push(w);
    }
    const res = [];
    for (let i = maxFreq; i >= 1; i--) {
        if (buckets[i].length) {
            buckets[i].sort();
            for (const w of buckets[i]) {
                res.push(w);
                if (res.length === k) return res;
            }
        }
    }
    return res;
}

// Driver code
const words = ["i", "love", "leetcode", "i", "love", "coding"];
const k = 2;
console.log(topKFrequent(words, k)); // Expected: ['i', 'love']

Line Notes

let maxFreq = 0;Track max frequency for bucket size

const buckets = Array.from({ length: maxFreq + 1 }, () => []);Create buckets array

buckets[count].push(w);Add word to bucket by frequency

for (let i = maxFreq; i >= 1; i--)Iterate buckets from high to low

buckets[i].sort();Sort bucket lexicographically

if (res.length === k) return res;Return once k words collected

⏱

Complexity

TimeO(n)

SpaceO(n)

Counting frequencies is O(n). Buckets array size is at most n. Sorting inside buckets is O(m log m) but total sorting cost is small since words are distributed. Overall near linear.

💡 For large n, this approach is fastest because it avoids sorting all words at once.

Interview Verdict: Accepted and optimal for large inputs

This is the best approach for interviews when asked for optimal time complexity.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, approach 2 (min heap) is a good balance of clarity and efficiency. Approach 3 (bucket sort) is optimal but slightly more complex.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n log n)	O(n)	No	N/A	Mention only - never code
2. Min Heap	O(n log k)	O(n)	No	N/A	Code this in 95% of interviews
3. Bucket Sort	O(n)	O(n)	No	N/A	Mention as optimal, code if asked for best

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Start with the brute force approach to show understanding.Explain why sorting all words is costly and introduce the min heap approach.Discuss the optimal bucket sort approach for best performance.Write clean code and test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to count frequencies, handle tie-breaking lexicographically, choose appropriate data structures, and optimize time complexity.

Common Follow-ups

• What if k is very large (close to number of unique words)? → Use bucket sort or sorting all words.
• How to handle uppercase or punctuation? → Normalize input before processing.

💡 Follow-ups test your ability to adapt the solution to variations and handle input preprocessing.

🔍

Pattern Recognition

When to Use

Use this pattern when you need to find the top k frequent elements or words, especially when tie-breaking lexicographically is required.

Signature Phrases

'return the k most frequent words''if two words have the same frequency, the word with the lower alphabetical order comes first'

NOT This Pattern When

Problems that require just sorting or counting without top-k or frequency tie-breaks

Similar Problems

Top K Frequent Elements - same frequency extraction but with numbersKth Largest Element in an Array - selection by orderSort Characters By Frequency - frequency sorting with characters

Practice

1. Given the following Python code implementing Quickselect to find k closest points, what is the final returned list when called with points = [[1,3],[-2,2],[2,-2]] and k = 2?

from typing import List
import random

def kClosest(points: List[List[int]], k: int) -> List[List[int]]:
    def dist(i):
        return points[i][0]*points[i][0] + points[i][1]*points[i][1]

    def partition(left, right, pivot_index):
        pivot_dist = dist(pivot_index)
        points[pivot_index], points[right] = points[right], points[pivot_index]
        store_index = left
        for i in range(left, right):
            if dist(i) < pivot_dist:
                points[store_index], points[i] = points[i], points[store_index]
                store_index += 1
        points[right], points[store_index] = points[store_index], points[right]
        return store_index

    def quickselect(left, right, k_smallest):
        if left == right:
            return
        pivot_index = random.randint(left, right)
        pivot_index = partition(left, right, pivot_index)
        if k_smallest == pivot_index:
            return
        elif k_smallest < pivot_index:
            quickselect(left, pivot_index - 1, k_smallest)
        else:
            quickselect(pivot_index + 1, right, k_smallest)

    quickselect(0, len(points) - 1, k - 1)
    return points[:k]

print(kClosest(points, k))

easy

A. [[2,-2], [1,3]]

B. [[1,3], [-2,2]]

C. [[-2,2], [2,-2]]

D. [[-2,2], [1,3]]

Solution

1. Step 1: Calculate squared distances

   Distances: [1,3] -> 10, [-2,2] -> 8, [2,-2] -> 8.

2. Step 2: Quickselect partitions to find 2 closest points

   Points with distance 8 are closest, so the two closest points are [-2,2] and [2,-2].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Returned points have smallest squared distances [OK]

Hint: Squared distances avoid sqrt and preserve order [OK]

Common Mistakes:

• Confusing order of points after partition
• Off-by-one errors in slicing points[:k]

2. You are given an n x n matrix where each row and each column is sorted in ascending order. You need to find the kth smallest element in the matrix efficiently. Which of the following approaches guarantees the optimal time complexity for this problem?

easy

A. Use a brute force approach by flattening the matrix into a list and sorting it.

B. Perform a binary search on the value range between the smallest and largest elements, counting how many elements are less than or equal to mid.

C. Use a dynamic programming approach to build a table of smallest elements up to k.

D. Use a greedy approach by repeatedly picking the smallest element from the first row and first column.

Solution

1. Step 1: Understand problem constraints

   The matrix is sorted both row-wise and column-wise, allowing binary search on the value range.

2. Step 2: Identify optimal approach

   Binary search on the value range uses the sorted property to count elements ≤ mid efficiently, achieving O(n log(max-min)) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search on values leverages matrix sorting [OK]

Hint: Binary search on values exploits matrix sorting [OK]

Common Mistakes:

• Thinking brute force or greedy is optimal
• Confusing DP with this problem

3. Consider the following Python code implementing the optimal bucket sort approach for top k frequent elements. What is the value of buckets[2] after the frequency dictionary is built for input nums = [1,1,2,2,3] and k = 2?

easy

A. [2]

B. [1, 2]

C. [1]

D. [3]

Solution

1. Step 1: Build frequency dictionary for nums = [1,1,2,2,3]

   Frequencies: 1 -> 2, 2 -> 2, 3 -> 1

2. Step 2: Assign elements to buckets by frequency

   buckets[1] = [3], buckets[2] = [1, 2]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Both 1 and 2 appear twice, so they share bucket 2 [OK]

Hint: Elements grouped by frequency in buckets [OK]

Common Mistakes:

• Confusing frequency counts
• Misindexing buckets by frequency

4. What is the average and worst-case time complexity of the Quickselect algorithm used to find the k closest points to the origin among n points, and why might the worst case occur?

medium

A. Average O(n log n), worst O(n^2) because partitioning always splits the array in half.

B. Average O(n), worst O(n^2) because poor pivot choices can lead to unbalanced partitions.

C. Average O(n^2), worst O(n^2) because all points must be compared to the pivot each time.

D. Average O(n), worst O(n log n) because recursion depth is limited by log n.

Solution

1. Step 1: Understand average case

   Quickselect partitions the array and reduces problem size each iteration, leading to average O(n) time.

2. Step 2: Understand worst case

   Poor pivot choices (e.g., always smallest or largest) cause unbalanced partitions, leading to O(n^2) worst-case time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Worst case arises from skewed partitions, average case benefits from balanced splits [OK]

Hint: Worst case is quadratic due to bad pivot choices [OK]

Common Mistakes:

• Assuming average case is O(n log n)
• Confusing quickselect with quicksort complexity

5. The following code attempts to find the kth smallest element in a sorted matrix using binary search on the value range. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line with 'if matrix[row][col] < mid:' inside countLessEqual

B. Line with 'low, high = matrix[0][0], matrix[-1][-1]'

C. Line with 'if countLessEqual(mid) < k:' inside while loop

D. Line with 'return low' at the end

Solution

1. Step 1: Examine countLessEqual condition

   The condition uses '<' instead of '<=' which causes elements equal to mid to be excluded from count.

2. Step 2: Understand impact on binary search

   Excluding elements equal to mid causes countLessEqual to undercount, leading binary search to converge incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing '<' to '<=' fixes counting and correctness [OK]

Hint: Counting ≤ mid must include equality [OK]

Common Mistakes:

• Using '<' instead of '<=' in count function
• Off-by-one in binary search updates