Top K Frequent Elements

🎯

Top K Frequent Elements

mediumHASH_MAPFacebookAmazonGoogle

Imagine you are analyzing a large dataset of user actions and want to quickly find the most common actions performed.

💡 This problem is about counting how often each element appears and then efficiently retrieving the top K elements by frequency. Beginners often struggle because they try to sort the entire dataset or don't know how to efficiently track frequencies and retrieve top elements.

📋

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4k is in the range [1, the number of unique elements in the array]

💡

Example

Input"nums = [1,1,1,2,2,3], k = 2"

Output[1,2]

1 appears 3 times, 2 appears 2 times, 3 appears once. The top 2 frequent elements are 1 and 2.

• All elements are the same → return that element
• k equals number of unique elements → return all elements
• Array with negative and positive numbers → handle negative keys correctly
• k equals 1 and multiple elements have same frequency → return any one of the top frequent

⚠️

Common Mistakes

Sorting the entire nums array instead of unique elements

Leads to incorrect results and unnecessary overhead

✅ Sort only the unique elements based on frequency

Using max-heap instead of min-heap for top k elements

Heap size grows unnecessarily, increasing time complexity

✅ Use a min-heap of size k to keep only top k frequent elements

Not handling the case when multiple elements have the same frequency

Output may be inconsistent or incorrect

✅ Accept any order or clarify with interviewer; bucket sort naturally groups ties

Forgetting to check if k is valid or equals number of unique elements

May cause index errors or incomplete results

✅ Validate k and handle edge cases explicitly

Using inefficient sorting or heap operations on large inputs

Solution times out or is too slow

✅ Use bucket sort or min-heap approach for better performance

🧠

Brute Force (Frequency Counting + Sorting Entire Array)

💡 This approach exists to build intuition by directly counting frequencies and sorting all elements by frequency, which is straightforward but inefficient for large inputs.

Intuition

Count how many times each element appears, then sort all unique elements by their frequency in descending order, and pick the top k.

Algorithm

1. Count the frequency of each element using a hash map.
2. Extract the unique elements into a list.
3. Sort the list based on frequency in descending order.
4. Return the first k elements from the sorted list.

💡 Sorting all unique elements by frequency is easy to understand but can be slow if there are many unique elements.

</>

Code

from typing import List

def topKFrequent(nums: List[int], k: int) -> List[int]:
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    unique = list(freq.keys())
    unique.sort(key=lambda x: freq[x], reverse=True)
    return unique[:k]

# Driver code
if __name__ == '__main__':
    print(topKFrequent([1,1,1,2,2,3], 2))  # Output: [1, 2]

Line Notes

freq = {}Initialize a dictionary to count frequencies of elements

for num in nums:Iterate over each number to build frequency map

freq[num] = freq.get(num, 0) + 1Increment frequency count for current number

unique = list(freq.keys())Extract unique elements to a list for sorting

unique.sort(key=lambda x: freq[x], reverse=True)Sort unique elements by their frequency in descending order

return unique[:k]Return the top k frequent elements

import java.util.*;

public class Solution {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        List<Integer> unique = new ArrayList<>(freq.keySet());
        unique.sort((a, b) -> freq.get(b) - freq.get(a));
        return unique.subList(0, k);
    }

    public static void main(String[] args) {
        System.out.println(topKFrequent(new int[]{1,1,1,2,2,3}, 2)); // Output: [1, 2]
    }
}

Line Notes

Map<Integer, Integer> freq = new HashMap<>();Create a map to store frequency counts

for (int num : nums)Iterate over input array to count frequencies

freq.put(num, freq.getOrDefault(num, 0) + 1);Update frequency count for each number

List<Integer> unique = new ArrayList<>(freq.keySet());Get list of unique elements

unique.sort((a, b) -> freq.get(b) - freq.get(a));Sort unique elements by frequency descending

return unique.subList(0, k);Return top k frequent elements

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

using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) {
        freq[num]++;
    }
    vector<int> unique;
    for (auto& p : freq) {
        unique.push_back(p.first);
    }
    sort(unique.begin(), unique.end(), [&](int a, int b) {
        return freq[a] > freq[b];
    });
    unique.resize(k);
    return unique;
}

int main() {
    vector<int> nums = {1,1,1,2,2,3};
    vector<int> res = topKFrequent(nums, 2);
    for (int x : res) cout << x << ' ';
    cout << '\n'; // Output: 1 2
    return 0;
}

Line Notes

unordered_map<int, int> freq;Use hash map to count frequencies efficiently

for (int num : nums)Iterate over input to build frequency map

freq[num]++;Increment frequency count for each element

vector<int> unique;Store unique elements for sorting

sort(unique.begin(), unique.end(), [&](int a, int b)Sort unique elements by frequency descending

unique.resize(k);Keep only top k elements after sorting

function topKFrequent(nums, k) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    const unique = Array.from(freq.keys());
    unique.sort((a, b) => freq.get(b) - freq.get(a));
    return unique.slice(0, k);
}

// Test
console.log(topKFrequent([1,1,1,2,2,3], 2)); // Output: [1, 2]

Line Notes

const freq = new Map();Initialize a Map to count frequencies

for (const num of nums)Iterate over input array to build frequency map

freq.set(num, (freq.get(num) || 0) + 1);Increment frequency count for current number

const unique = Array.from(freq.keys());Extract unique elements for sorting

unique.sort((a, b) => freq.get(b) - freq.get(a));Sort unique elements by frequency descending

return unique.slice(0, k);Return the top k frequent elements

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Counting frequencies takes O(n). Sorting unique elements takes O(m log m), where m is number of unique elements, up to n. Overall O(n log n) in worst case.

💡 For n=100,000, sorting all unique elements can be very slow, so this approach is not efficient for large inputs.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large inputs, so we need better methods.

🧠

Better Approach (Frequency Map + Min-Heap)

💡 This approach improves efficiency by using a min-heap to keep track of the top k frequent elements without sorting all unique elements.

Intuition

Count frequencies, then maintain a min-heap of size k to store the top k elements by frequency. This avoids sorting all elements.

Algorithm

1. Count the frequency of each element using a hash map.
2. Create a min-heap to store elements by frequency.
3. Iterate over frequency map, push elements into the heap.
4. If heap size exceeds k, pop the smallest frequency element.
5. After processing all, extract elements from heap as result.

💡 Using a min-heap keeps only the top k frequent elements, reducing sorting overhead.

</>

Code

from typing import List
import heapq

def topKFrequent(nums: List[int], k: int) -> List[int]:
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    heap = []
    for num, count in freq.items():
        heapq.heappush(heap, (count, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for count, num in heap]

# Driver code
if __name__ == '__main__':
    print(topKFrequent([1,1,1,2,2,3], 2))  # Output: [2, 1]

Line Notes

freq = {}Initialize frequency dictionary

for num in nums:Count frequency of each number

heap = []Initialize min-heap to track top k elements

heapq.heappush(heap, (count, num))Push current element with frequency into heap

if len(heap) > k:If heap exceeds size k, remove smallest frequency element

return [num for count, num in heap]Extract elements from heap as result

import java.util.*;

public class Solution {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
            Comparator.comparingInt(Map.Entry::getValue));
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            heap.offer(entry);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        List<Integer> res = new ArrayList<>();
        while (!heap.isEmpty()) {
            res.add(heap.poll().getKey());
        }
        Collections.reverse(res); // Reverse to match descending frequency order
        return res;
    }

    public static void main(String[] args) {
        System.out.println(topKFrequent(new int[]{1,1,1,2,2,3}, 2)); // Output: [1, 2]
    }
}

Line Notes

Map<Integer, Integer> freq = new HashMap<>();Create frequency map

for (int num : nums)Count frequencies

PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(...)Min-heap based on frequency

heap.offer(entry);Add entry to heap

if (heap.size() > k)Maintain heap size at most k

while (!heap.isEmpty())Extract top k elements from heap

Collections.reverse(res);Reverse result to get descending frequency order

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

using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) {
        freq[num]++;
    }
    // Comparator for min-heap by frequency
    auto cmp = [&](pair<int,int>& a, pair<int,int>& b) { return a.first > b.first; };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> heap(cmp);
    for (auto& p : freq) {
        heap.push({p.second, p.first});
        if ((int)heap.size() > k) heap.pop();
    }
    vector<int> res;
    while (!heap.empty()) {
        res.push_back(heap.top().second);
        heap.pop();
    }
    reverse(res.begin(), res.end()); // Reverse to get descending frequency order
    return res;
}

int main() {
    vector<int> nums = {1,1,1,2,2,3};
    vector<int> res = topKFrequent(nums, 2);
    for (int x : res) cout << x << ' ';
    cout << '\n'; // Output: 1 2
    return 0;
}

Line Notes

unordered_map<int, int> freq;Count frequencies using hash map

auto cmp = [&](pair<int,int>& a, pair<int,int>& b)Comparator for min-heap by frequency

priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> heap(cmp);Min-heap to keep top k frequent elements

heap.push({p.second, p.first});Push frequency and element pair into heap

if ((int)heap.size() > k) heap.pop();Pop smallest frequency if heap size exceeds k

while (!heap.empty())Extract elements from heap for result

reverse(res.begin(), res.end());Reverse result to get descending frequency order

function topKFrequent(nums, k) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    const heap = [];
    const pushHeap = (pair) => {
        heap.push(pair);
        heap.sort((a, b) => a[0] - b[0]);
        if (heap.length > k) heap.shift();
    };
    for (const [num, count] of freq.entries()) {
        pushHeap([count, num]);
    }
    return heap.map(pair => pair[1]);
}

// Test
console.log(topKFrequent([1,1,1,2,2,3], 2)); // Output: [2, 1]

Line Notes

const freq = new Map();Initialize frequency map

for (const num of nums)Count frequencies

const heap = [];Use array as min-heap substitute

heap.push(pair);Add frequency-element pair to heap

heap.sort((a, b) => a[0] - b[0]);Sort heap to maintain min-heap property

if (heap.length > k) heap.shift();Remove smallest frequency element if heap too big

return heap.map(pair => pair[1]);Extract elements from heap as result

⏱

Complexity

TimeO(n log k)

SpaceO(n)

Counting frequencies is O(n). Each insertion into heap is O(log k), done for m unique elements, so O(m log k). Since m ≤ n, total O(n log k).

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

Interview Verdict: Accepted and efficient for large inputs

This approach balances speed and simplicity, suitable for most interview scenarios.

🧠

Optimal Approach (Bucket Sort)

💡 This approach uses bucket sort to achieve linear time complexity by grouping elements by frequency, avoiding sorting or heap operations.

Intuition

Since frequency ranges from 1 to n, create buckets where index represents frequency and each bucket holds elements with that frequency. Then iterate buckets from high to low frequency to collect top k elements.

Algorithm

1. Count frequency of each element using a hash map.
2. Create an array of buckets where index is frequency, each bucket holds elements with that frequency.
3. Place each element into its corresponding frequency bucket.
4. Iterate buckets from highest frequency to lowest, collecting elements until k are collected.
5. Return the collected elements.

💡 Bucket sort leverages the limited frequency range to avoid expensive sorting or heap operations.

</>

Code

from typing import List

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

# Driver code
if __name__ == '__main__':
    print(topKFrequent([1,1,1,2,2,3], 2))  # Output: [1, 2]

Line Notes

freq = {}Initialize frequency dictionary

for num in nums:Count frequency of each element

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

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

buckets[count].append(num)Place element in bucket corresponding to its frequency

for i in range(max_freq, 0, -1)Iterate buckets from highest frequency down

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

import java.util.*;

public class Solution {
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        int maxFreq = Collections.max(freq.values());
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i <= maxFreq; i++) {
            buckets.add(new ArrayList<>());
        }
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            buckets.get(entry.getValue()).add(entry.getKey());
        }
        List<Integer> res = new ArrayList<>();
        for (int i = maxFreq; i >= 1 && res.size() < k; i--) {
            for (int num : buckets.get(i)) {
                res.add(num);
                if (res.size() == k) return res;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(topKFrequent(new int[]{1,1,1,2,2,3}, 2)); // Output: [1, 2]
    }
}

Line Notes

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

int maxFreq = Collections.max(freq.values());Find max frequency for bucket size

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

buckets.get(entry.getValue()).add(entry.getKey());Add element to corresponding frequency bucket

for (int i = maxFreq; i >= 1 && res.size() < k; i--)Iterate buckets from high to low frequency

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

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

using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) {
        freq[num]++;
    }
    int maxFreq = 0;
    for (auto& p : freq) {
        maxFreq = max(maxFreq, p.second);
    }
    vector<vector<int>> buckets(maxFreq + 1);
    for (auto& p : freq) {
        buckets[p.second].push_back(p.first);
    }
    vector<int> res;
    for (int i = maxFreq; i >= 1 && (int)res.size() < k; i--) {
        for (int num : buckets[i]) {
            res.push_back(num);
            if ((int)res.size() == k) return res;
        }
    }
    return res;
}

int main() {
    vector<int> nums = {1,1,1,2,2,3};
    vector<int> res = topKFrequent(nums, 2);
    for (int x : res) cout << x << ' ';
    cout << '\n'; // Output: 1 2
    return 0;
}

Line Notes

unordered_map<int, int> freq;Count frequencies

int maxFreq = 0;Track maximum frequency

vector<vector<int>> buckets(maxFreq + 1);Create buckets indexed by frequency

buckets[p.second].push_back(p.first);Add element to bucket for its frequency

for (int i = maxFreq; i >= 1 && (int)res.size() < k; i--)Iterate buckets from high to low frequency

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

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

// Test
console.log(topKFrequent([1,1,1,2,2,3], 2)); // Output: [1, 2]

Line Notes

const freq = new Map();Count frequencies

const maxFreq = Math.max(...freq.values());Find maximum frequency

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

buckets[count].push(num);Add element to bucket for its frequency

for (let i = maxFreq; i > 0 && res.length < k; i--)Iterate buckets from high to low frequency

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

⏱

Complexity

TimeO(n)

SpaceO(n)

Counting frequencies is O(n). Creating buckets and iterating them is O(n) since total elements are n. No sorting or heap operations needed.

💡 For n=100,000, this approach is very fast and scalable.

Interview Verdict: Accepted and optimal

This is the best approach in terms of time complexity and is recommended if you can implement it correctly.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, approach 2 (min-heap) or 3 (bucket sort) is preferred for efficiency and clarity.

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	Good balance of efficiency and simplicity
3. Bucket Sort	O(n)	O(n)	No	N/A	Optimal approach if comfortable implementing

💼

Interview Strategy

💡 Use this guide to understand the problem deeply and practice all approaches. Start with brute force to build intuition, then improve efficiency step-by-step.

How to Present

Clarify the problem and constraints with the interviewer.State the brute force approach: count frequencies and sort all elements.Discuss its inefficiency and propose using a min-heap to track top k.Finally, explain the bucket sort approach for optimal linear time.Code the chosen approach carefully and test with examples.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your ability to count frequencies, choose appropriate data structures (hash map, heap, buckets), and optimize time complexity.

Common Follow-ups

• What if k equals the number of unique elements? → Return all elements sorted by frequency.
• How to handle ties in frequency? → Any order is acceptable unless specified.

💡 Follow-ups often test your understanding of edge cases and output ordering requirements.

🔍

Pattern Recognition

When to Use

1) Need to find most frequent elements; 2) Frequency counting is possible; 3) Output top k elements; 4) Efficient retrieval of top frequencies required.

Signature Phrases

top k frequent elementsmost common elementsfrequency of elements

NOT This Pattern When

Problems asking for kth largest element without frequency or sorting entire array

Similar Problems

Top K Frequent Words - similar frequency counting with stringsSort Characters By Frequency - frequency sorting of characters

Practice

1. The following code attempts to find the kth largest XOR coordinate value but contains a subtle bug. Identify the line with the bug.

medium

A. Line replacing min_heap root when val is greater than min_heap[0]

B. Line initializing prefix matrix with zeros

C. Line computing prefix[i][j] with XOR of prefix[i - 1][j], prefix[i][j - 1], and matrix[i - 1][j - 1]

D. Line pushing val into min_heap when heap size is less than k

Solution

1. Step 1: Examine prefix XOR formula

   The prefix XOR formula must XOR four terms: prefix[i-1][j], prefix[i][j-1], prefix[i-1][j-1], and matrix[i-1][j-1]. The code misses prefix[i-1][j-1].

2. Step 2: Understand impact of missing term

   Omitting prefix[i-1][j-1] causes incorrect prefix XOR values, leading to wrong kth largest results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct prefix XOR requires all four terms XORed [OK]

Hint: Prefix XOR requires XOR of four terms, not three [OK]

Common Mistakes:

• Forgetting prefix[i-1][j-1] in XOR
• Off-by-one errors in indexing
• Misusing heap operations

2. The following code attempts to find the maximum CPU load from a list of jobs. Identify the line containing the subtle bug that causes incorrect results in some cases.

def find_max_cpu_load(jobs):
    events = []
    for start, end, load in jobs:
        events.append((start, load))
        events.append((end, load))  # Bug here
    events.sort(key=lambda x: x[0])

    current_load = 0
    max_load = 0
    for _, load_change in events:
        current_load += load_change
        max_load = max(max_load, current_load)
    return max_load

medium

A. Line adding (end, load) instead of (end, -load) to events.

B. Line sorting events by start time only.

C. Line initializing current_load to 0 before loop.

D. Line updating max_load inside the loop.

Solution

1. Step 1: Identify event creation lines.

   Start events add positive load, end events must subtract load.

2. Step 2: Spot that (end, load) incorrectly adds load instead of subtracting.

   This causes current_load to accumulate incorrectly, inflating max_load.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   End event load must be negative to reduce current load [OK]

Hint: End events must subtract load, not add [OK]

Common Mistakes:

• Forgetting negative load at job end
• Misordering events with same timestamp

3. Suppose you want to find the kth largest element in an array where elements can be repeated and you want to find the kth largest unique element instead. Which modification to the Quickselect approach is correct?

hard

A. Use a min-heap of size k to store unique elements only, ignoring duplicates during insertion.

B. Run Quickselect as usual and then scan left and right to skip duplicates until kth unique is found.

C. Sort the array fully and iterate from largest to smallest counting unique elements until kth unique is reached.

D. Modify partition to skip duplicates and recurse only on unique elements.

Solution

1. Step 1: Understand uniqueness constraint

   Quickselect partitions by value but does not handle uniqueness inherently.

2. Step 2: Evaluate modifications

   Partial scanning or modifying partition is complex and error-prone; min-heap requires extra checks.

3. Step 3: Choose reliable approach

   Sorting fully and counting unique elements is straightforward and guarantees correctness.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Full sort enables unique counting easily [OK]

Hint: Uniqueness requires full sort or extra data structures [OK]

Common Mistakes:

• Assuming Quickselect handles uniqueness
• Trying to modify partition without correctness
• Ignoring duplicates in heap approach

4. Suppose the problem changes: you want to find the kth largest XOR coordinate value, but now the matrix can contain negative integers. Which modification to the optimal prefix XOR + min-heap approach is necessary to handle this correctly?

hard

A. Use a 64-bit integer type to store prefix XOR values to avoid sign issues.

B. Convert all negative integers to positive before computing prefix XOR.

C. No modification needed; XOR works the same with negative integers.

D. Use bitwise AND instead of XOR to handle negative values correctly.

Solution

1. Step 1: Understand XOR with negative integers

   In Python, integers are unbounded but negative numbers use two's complement representation internally, which can cause sign extension issues if stored in fixed-width types.

2. Step 2: Use 64-bit integer type for prefix XOR

   To correctly handle negative values and avoid sign extension or overflow, use a 64-bit integer type (e.g., numpy.int64) for prefix XOR computations and heap storage.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Handling negative integers requires careful data type choice, not changing XOR logic [OK]

Hint: XOR logic unchanged; data type must handle sign correctly [OK]

Common Mistakes:

• Assuming XOR fails with negatives
• Replacing XOR with AND
• Ignoring integer overflow/sign issues

5. Suppose the problem changes: now characters can be reused unlimited times (like infinite supply), and you want to return a string of length k with characters sorted by frequency descending. Which modification to the bucket sort approach correctly handles this variant?

hard

A. Use a max heap to repeatedly extract the highest frequency character and append it until length k is reached, decrementing frequency each time.

B. Use the same bucket sort but truncate the final concatenated string to length k.

C. Use bucket sort but repeat characters infinitely in buckets until length k is reached.

D. Sort characters by frequency once, then repeat the entire sorted string until length k is reached.

Solution

1. Step 1: Understand infinite reuse constraint

   Characters can be used multiple times, frequencies decrease as used.

2. Step 2: Why max heap is needed

   Max heap allows extracting highest frequency char, appending it, then updating frequency dynamically.

3. Step 3: Why bucket sort fails here

   Bucket sort assumes fixed frequencies; infinite reuse requires dynamic frequency updates.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Max heap supports dynamic frequency changes and repeated extraction [OK]

Hint: Infinite reuse needs dynamic frequency updates, not static buckets [OK]

Common Mistakes:

• Truncating static bucket sort output
• Repeating entire sorted string ignoring frequencies