DSA-070 · FOCUSED PRACTICE
Top K Frequent Elements
Core · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 36235 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the k most frequent distinct values from an int array, ordered by descending frequency and then ascending numeric value. Use a bounded heap for selection, and preserve the input.
- nums is nonnull with at most 100,000 arbitrary ints. Let u be its distinct-value count. Require 0<=k<=u; invalid k throws IllegalArgumentException. Null throws NullPointerException. Empty input permits only k=0.
- Return a fresh int[k] containing distinct values in exact rank order: higher count first, smaller value first on ties. k counts distinct keys, not occurrences. k=0 returns a fresh empty array.
- Neither approach modifies nums. HashMap iteration order and PriorityQueue internal/iteration order are unspecified; the final result is explicitly sorted by the rank comparator. Walkthrough candidate order is illustrative first-occurrence order, not a promise about Java map traversal.
Examples
Input:
nums=[4,4,1,1,2,3], k=2
Output:[1,4]Both 1 and 4 occur twice, so smaller value 1 precedes 4.
Input:
nums=[−1,−1,2,3], k=3
Output:[−1,2,3]Frequency outranks numeric magnitude. The final two keys tie at count one.
Input:
nums=[], k=0
Output:fresh []The rank set is empty and no value sentinel is needed.
Before you start
- Frequency maps and distinct values versus occurrences
- PriorityQueue comparator direction and deterministic ties
Recognize the structure
First collapse occurrences into key frequencies. The selection priority is count with a declared tie rule, not the original value itself. To retain the best k, the heap must expose the worst selected candidate so each overflow removes the least useful key.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 127/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
How many times does each distinct key occur?
Hint 2
Which selected candidate should be easiest to evict when the heap exceeds k?
Hint 3
Use the reverse of the final count/value rank for the heap root, trim after each insertion, and sort the survivors.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Count, sort all distinct keys, and take k
Count all keys, create (value,count) records, sort by descending count then ascending value, and return the first k values. For [4,4,1,1,2,3], the full rank is [1,4,2,3]. This uses O(n+u log(u+1)) expected time and O(u) auxiliary storage, plus k output values. The bounded heap avoids sorting all u keys when k is small, but deterministic final output still needs sorting the retained k.
Improve the baseline
Build counts and validate k
A key appears once in the candidate set regardless of its frequency. Count all input occurrences, then validate against the number of distinct keys, not nums.length.
Reverse the output rank at the heap root
BEST orders higher count first and smaller value first. BEST.reversed() puts lower count and then larger value at the root: exactly the worst retained candidate. Offer each key once and poll whenever size exceeds k.
Sort the retained set for return
The heap certifies membership, not output order. Copy its entries, sort by BEST, and emit values. On tied counts, removing a larger value before a smaller one implements the promised deterministic boundary policy.
Why it is correct
Frequency correctness
After counting, each key’s stored count equals its number of input occurrences, with no duplicate candidate records.
Selection invariant
After processing any candidate prefix, the heap contains the best min(k,processedKeys) records by the total count/value rank. Adding one record creates at most k+1 candidates; removing the worst leaves exactly the best k. The invariant does not depend on candidate enumeration order.
Output correctness
Every key is eventually considered, so the retained set is the global top k. Sorting that set by the same total rank produces the required order, preserves key uniqueness, and allocates output independently of nums.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
public final class Solution {
private record Entry(int value, int count) {}
private static final Comparator<Entry> BEST = Comparator.comparingInt(Entry::count).reversed().thenComparingInt(Entry::value);
private static Map<Integer,Integer> counts(int[] nums, int k) {
Objects.requireNonNull(nums, "nums");
Map<Integer,Integer> counts = new HashMap<>();
for (int value : nums) counts.merge(value, 1, Integer::sum);
if (k < 0 || k > counts.size()) throw new IllegalArgumentException("k outside unique count");
return counts;
}
public static int[] topK(int[] nums, int k) {
Map<Integer,Integer> counts = counts(nums, k);
PriorityQueue<Entry> selected = new PriorityQueue<>(BEST.reversed());
for (Map.Entry<Integer,Integer> item : counts.entrySet()) {
selected.offer(new Entry(item.getKey(), item.getValue()));
if (selected.size() > k) selected.poll();
}
ArrayList<Entry> ordered = new ArrayList<>(selected);
ordered.sort(BEST);
return ordered.stream().mapToInt(Entry::value).toArray();
}
public static int[] baseline(int[] nums, int k) {
Map<Integer,Integer> counts = counts(nums, k);
ArrayList<Entry> all = new ArrayList<>();
counts.forEach((value,count) -> all.add(new Entry(value,count)));
all.sort(BEST);
return all.subList(0,k).stream().mapToInt(Entry::value).toArray();
}
}
Read the meaningful blocks
Safe comparators
Comparator.comparingInt(...).reversed().thenComparingInt(...) avoids count or value subtraction, including MIN/MAX keys.
Offer then trim
The heap can temporarily hold k+1 entries. It never grows with u, and k=0 simply discards every candidate after counting.
Do not return heap iteration
new ArrayList<>(selected) is an unordered heap copy until ordered.sort(BEST) runs. Sorting the display likewise does not describe the queue’s internal array.
Complexity
Expected time is O(n+u log(k+1)+k log(k+1)) for k>=1, including deterministic output sorting; k=0 takes O(n). Counting contributes the HashMap expectation. Peak auxiliary storage is O(u+k), plus O(k) returned values.
The full-sort baseline takes O(n+u log(u+1)) expected time and O(u) auxiliary storage. Frequency buckets can avoid comparison selection, but deterministic numeric ties may still require ordering within buckets.
Exact-state walkthroughs
Reveal normal and boundary traces
Count ties select smaller values
Input: {"nums":[4,4,1,1,2,3],"k":2} · Result: [1,4]
Step 1 of 7: Count all keys before selecting.
Candidates are shown in illustrative first-occurrence order; Java HashMap iteration is unspecified. Heap display is worst-priority first, not internal queue storage.
k=2. Candidate keys processed: 0. Map candidate order is illustrative, while final ties are deterministic.
Counted distinct keys
- 4: count 2
- 1: count 2
- 2: count 1
- 3: count 1
Retained candidates — lower count / larger value is worse
Empty.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| values | [4,4,1,1,2,3] |
| k | 2 |
| frequencies | [{"value":4,"count":2},{"value":1,"count":2},{"value":2,"count":1},{"value":3,"count":1}] |
| heap | [] |
| phase | "initial" |
| processed | 0 |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Comparator; 3 import java.util.HashMap; 4 import java.util.Map; 5 import java.util.Objects; 6 import java.util.PriorityQueue; 7 public final class Solution { 8 private record Entry(int value, int count) {} 9 private static final Comparator<Entry> BEST = Comparator.comparingInt(Entry::count).reversed().thenComparingInt(Entry::value); 10 private static Map<Integer,Integer> counts(int[] nums, int k) { 11 Objects.requireNonNull(nums, "nums"); 12 Map<Integer,Integer> counts = new HashMap<>(); 13 for (int value : nums) counts.merge(value, 1, Integer::sum); 14 if (k < 0 || k > counts.size()) throw new IllegalArgumentException("k outside unique count"); 15 return counts; 16 } 17 public static int[] topK(int[] nums, int k) { 18 Map<Integer,Integer> counts = counts(nums, k); 19 PriorityQueue<Entry> selected = new PriorityQueue<>(BEST.reversed()); 20 for (Map.Entry<Integer,Integer> item : counts.entrySet()) { 21 selected.offer(new Entry(item.getKey(), item.getValue())); 22 if (selected.size() > k) selected.poll(); 23 } 24 ArrayList<Entry> ordered = new ArrayList<>(selected); 25 ordered.sort(BEST); 26 return ordered.stream().mapToInt(Entry::value).toArray(); 27 } 28 public static int[] baseline(int[] nums, int k) { 29 Map<Integer,Integer> counts = counts(nums, k); 30 ArrayList<Entry> all = new ArrayList<>(); 31 counts.forEach((value,count) -> all.add(new Entry(value,count))); 32 all.sort(BEST); 33 return all.subList(0,k).stream().mapToInt(Entry::value).toArray(); 34 } 35 } 36
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Count all keys before selecting.
Candidates are shown in illustrative first-occurrence order; Java HashMap iteration is unspecified. Heap display is worst-priority first, not internal queue storage.
- values
[4,4,1,1,2,3]- k
2- frequencies
[{"value":4,"count":2},{"value":1,"count":2},{"value":2,"count":1},{"value":3,"count":1}]- heap
[]- phase
"initial"- processed
0
- Offer one distinct candidate and trim the worst rank.
The retained set is the best min(k,processed keys), ordered by count then smaller value; equal keys never become duplicate candidates.
- values
[4,4,1,1,2,3]- k
2- frequencies
[{"value":4,"count":2},{"value":1,"count":2},{"value":2,"count":1},{"value":3,"count":1}]- heap
[{"value":4,"count":2}]- phase
"select"- processed
1- candidate
{"value":4,"count":2}- discarded
null
- Offer one distinct candidate and trim the worst rank.
The retained set is the best min(k,processed keys), ordered by count then smaller value; equal keys never become duplicate candidates.
- values
[4,4,1,1,2,3]- k
2- frequencies
[{"value":4,"count":2},{"value":1,"count":2},{"value":2,"count":1},{"value":3,"count":1}]- heap
[{"value":4,"count":2},{"value":1,"count":2}]- phase
"select"- processed
2- candidate
{"value":1,"count":2}- discarded
null
- Offer one distinct candidate and trim the worst rank.
The retained set is the best min(k,processed keys), ordered by count then smaller value; equal keys never become duplicate candidates.
- values
[4,4,1,1,2,3]- k
2- frequencies
[{"value":4,"count":2},{"value":1,"count":2},{"value":2,"count":1},{"value":3,"count":1}]- heap
[{"value":4,"count":2},{"value":1,"count":2}]- phase
"select"- processed
3- candidate
{"value":2,"count":1}- discarded
{"value":2,"count":1}
- Offer one distinct candidate and trim the worst rank.
The retained set is the best min(k,processed keys), ordered by count then smaller value; equal keys never become duplicate candidates.
- values
[4,4,1,1,2,3]- k
2- frequencies
[{"value":4,"count":2},{"value":1,"count":2},{"value":2,"count":1},{"value":3,"count":1}]- heap
[{"value":4,"count":2},{"value":1,"count":2}]- phase
"select"- processed
4- candidate
{"value":3,"count":1}- discarded
{"value":3,"count":1}
- Sort only selected entries for deterministic output.
PriorityQueue iteration does not specify return order; explicit sorting establishes count-descending/value-ascending output.
- values
[4,4,1,1,2,3]- k
2- frequencies
[{"value":4,"count":2},{"value":1,"count":2},{"value":2,"count":1},{"value":3,"count":1}]- heap
[{"value":4,"count":2},{"value":1,"count":2}]- phase
"ordered"- processed
4- ordered
[{"value":1,"count":2},{"value":4,"count":2}]
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
[1,4]
Zero requested keys
Input: {"nums":[7,7],"k":0} · Result: []
Step 1 of 4: Count all keys before selecting.
Candidates are shown in illustrative first-occurrence order; Java HashMap iteration is unspecified. Heap display is worst-priority first, not internal queue storage.
k=0. Candidate keys processed: 0. Map candidate order is illustrative, while final ties are deterministic.
Counted distinct keys
- 7: count 2
Retained candidates — lower count / larger value is worse
Empty.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| values | [7,7] |
| k | 0 |
| frequencies | [{"value":7,"count":2}] |
| heap | [] |
| phase | "initial" |
| processed | 0 |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Comparator; 3 import java.util.HashMap; 4 import java.util.Map; 5 import java.util.Objects; 6 import java.util.PriorityQueue; 7 public final class Solution { 8 private record Entry(int value, int count) {} 9 private static final Comparator<Entry> BEST = Comparator.comparingInt(Entry::count).reversed().thenComparingInt(Entry::value); 10 private static Map<Integer,Integer> counts(int[] nums, int k) { 11 Objects.requireNonNull(nums, "nums"); 12 Map<Integer,Integer> counts = new HashMap<>(); 13 for (int value : nums) counts.merge(value, 1, Integer::sum); 14 if (k < 0 || k > counts.size()) throw new IllegalArgumentException("k outside unique count"); 15 return counts; 16 } 17 public static int[] topK(int[] nums, int k) { 18 Map<Integer,Integer> counts = counts(nums, k); 19 PriorityQueue<Entry> selected = new PriorityQueue<>(BEST.reversed()); 20 for (Map.Entry<Integer,Integer> item : counts.entrySet()) { 21 selected.offer(new Entry(item.getKey(), item.getValue())); 22 if (selected.size() > k) selected.poll(); 23 } 24 ArrayList<Entry> ordered = new ArrayList<>(selected); 25 ordered.sort(BEST); 26 return ordered.stream().mapToInt(Entry::value).toArray(); 27 } 28 public static int[] baseline(int[] nums, int k) { 29 Map<Integer,Integer> counts = counts(nums, k); 30 ArrayList<Entry> all = new ArrayList<>(); 31 counts.forEach((value,count) -> all.add(new Entry(value,count))); 32 all.sort(BEST); 33 return all.subList(0,k).stream().mapToInt(Entry::value).toArray(); 34 } 35 } 36
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Count all keys before selecting.
Candidates are shown in illustrative first-occurrence order; Java HashMap iteration is unspecified. Heap display is worst-priority first, not internal queue storage.
- values
[7,7]- k
0- frequencies
[{"value":7,"count":2}]- heap
[]- phase
"initial"- processed
0
- Offer one distinct candidate and trim the worst rank.
The retained set is the best min(k,processed keys), ordered by count then smaller value; equal keys never become duplicate candidates.
- values
[7,7]- k
0- frequencies
[{"value":7,"count":2}]- heap
[]- phase
"select"- processed
1- candidate
{"value":7,"count":2}- discarded
{"value":7,"count":2}
- Sort only selected entries for deterministic output.
PriorityQueue iteration does not specify return order; explicit sorting establishes count-descending/value-ascending output.
- values
[7,7]- k
0- frequencies
[{"value":7,"count":2}]- heap
[]- phase
"ordered"- processed
1- ordered
[]
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
[]
Extreme-key tie ordering
Input: {"nums":[2147483647,-2147483648,2147483647,-2147483648],"k":1} · Result: [-2147483648]
Step 1 of 5: Count all keys before selecting.
Candidates are shown in illustrative first-occurrence order; Java HashMap iteration is unspecified. Heap display is worst-priority first, not internal queue storage.
k=1. Candidate keys processed: 0. Map candidate order is illustrative, while final ties are deterministic.
Counted distinct keys
- 2147483647: count 2
- -2147483648: count 2
Retained candidates — lower count / larger value is worse
Empty.
Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.
| Variable | Value |
|---|---|
| values | [2147483647,-2147483648,2147483647,-2147483648] |
| k | 1 |
| frequencies | [{"value":2147483647,"count":2},{"value":-2147483648,"count":2}] |
| heap | [] |
| phase | "initial" |
| processed | 0 |
See the affected Java block
1 import java.util.ArrayList; 2 import java.util.Comparator; 3 import java.util.HashMap; 4 import java.util.Map; 5 import java.util.Objects; 6 import java.util.PriorityQueue; 7 public final class Solution { 8 private record Entry(int value, int count) {} 9 private static final Comparator<Entry> BEST = Comparator.comparingInt(Entry::count).reversed().thenComparingInt(Entry::value); 10 private static Map<Integer,Integer> counts(int[] nums, int k) { 11 Objects.requireNonNull(nums, "nums"); 12 Map<Integer,Integer> counts = new HashMap<>(); 13 for (int value : nums) counts.merge(value, 1, Integer::sum); 14 if (k < 0 || k > counts.size()) throw new IllegalArgumentException("k outside unique count"); 15 return counts; 16 } 17 public static int[] topK(int[] nums, int k) { 18 Map<Integer,Integer> counts = counts(nums, k); 19 PriorityQueue<Entry> selected = new PriorityQueue<>(BEST.reversed()); 20 for (Map.Entry<Integer,Integer> item : counts.entrySet()) { 21 selected.offer(new Entry(item.getKey(), item.getValue())); 22 if (selected.size() > k) selected.poll(); 23 } 24 ArrayList<Entry> ordered = new ArrayList<>(selected); 25 ordered.sort(BEST); 26 return ordered.stream().mapToInt(Entry::value).toArray(); 27 } 28 public static int[] baseline(int[] nums, int k) { 29 Map<Integer,Integer> counts = counts(nums, k); 30 ArrayList<Entry> all = new ArrayList<>(); 31 counts.forEach((value,count) -> all.add(new Entry(value,count))); 32 all.sort(BEST); 33 return all.subList(0,k).stream().mapToInt(Entry::value).toArray(); 34 } 35 } 36
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Count all keys before selecting.
Candidates are shown in illustrative first-occurrence order; Java HashMap iteration is unspecified. Heap display is worst-priority first, not internal queue storage.
- values
[2147483647,-2147483648,2147483647,-2147483648]- k
1- frequencies
[{"value":2147483647,"count":2},{"value":-2147483648,"count":2}]- heap
[]- phase
"initial"- processed
0
- Offer one distinct candidate and trim the worst rank.
The retained set is the best min(k,processed keys), ordered by count then smaller value; equal keys never become duplicate candidates.
- values
[2147483647,-2147483648,2147483647,-2147483648]- k
1- frequencies
[{"value":2147483647,"count":2},{"value":-2147483648,"count":2}]- heap
[{"value":2147483647,"count":2}]- phase
"select"- processed
1- candidate
{"value":2147483647,"count":2}- discarded
null
- Offer one distinct candidate and trim the worst rank.
The retained set is the best min(k,processed keys), ordered by count then smaller value; equal keys never become duplicate candidates.
- values
[2147483647,-2147483648,2147483647,-2147483648]- k
1- frequencies
[{"value":2147483647,"count":2},{"value":-2147483648,"count":2}]- heap
[{"value":-2147483648,"count":2}]- phase
"select"- processed
2- candidate
{"value":-2147483648,"count":2}- discarded
{"value":2147483647,"count":2}
- Sort only selected entries for deterministic output.
PriorityQueue iteration does not specify return order; explicit sorting establishes count-descending/value-ascending output.
- values
[2147483647,-2147483648,2147483647,-2147483648]- k
1- frequencies
[{"value":2147483647,"count":2},{"value":-2147483648,"count":2}]- heap
[{"value":-2147483648,"count":2}]- phase
"ordered"- processed
2- ordered
[{"value":-2147483648,"count":2}]
- Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
- result
[-2147483648]
Test the contract
Input:
[],k=0
Output:fresh []Empty policy.
Input:
[2,1],k=1
Output:[1]Tie at the selection boundary.
Input:
[9,1,1],k=1
Output:[1]Frequency before value.
Input:
[MIN,MAX,MIN,MAX,0],k=2
Output:[MIN,MAX]Safe deterministic extreme-key ties.
Input:
[1,1],k=2
Output:IllegalArgumentExceptionOnly one distinct key.
Common mistakes and counterexamples
Keep the largest numeric values
Counterexample: [9,1,1], k=1 must return 1, not 9.
Rank by frequency first.
Use a best-first heap and poll on overflow
Counterexample: Polling the highest count discards exactly the candidate that should survive.
Expose the worst retained record at the root.
Ignore a tie policy
Counterexample: [2,1], k=1 can fluctuate under unspecified map order if count ties are not resolved.
Define smaller value as better and use it in both selection and output comparators.
Treat heap iteration as sorted
Counterexample: PriorityQueue iteration need not follow poll order.
Sort the retained copy explicitly before returning it.
Follow-ups
Return top k words.
Use count descending then the declared lexicographic order. The same total rank must govern both eviction and final output; language/case/Unicode normalization policy matters.
Maintain top k under continuous count updates.
An ordinary PriorityQueue does not update an existing key’s priority automatically. Use indexed heaps, versioned lazy entries with bounded cleanup, or an ordered frequency structure, and account for retained stale state.
Use frequency buckets.
Counts range from 1 to n, so bucket membership can be linear. If deterministic smaller-value ties remain required, include the cost of ordering a tied bucket rather than claiming unconditional linear ordered output.