Top K frequent numbers
Medium
Java
Collections
32 views
Problem Statement
Task: return k numbers with highest frequency. If tie, any order is fine.
Input Format
An integer n (size of array)
Then n integers (array elements)
An integer k
Then n integers (array elements)
An integer k
Output Format
k numbers with the highest frequency.
(Any order is acceptable if frequencies are same)
(Any order is acceptable if frequencies are same)
Example
8 1 1 1 2 2 3 3 4 2
[1, 2]
Constraints
• n ≥ 1
• k ≥ 1
• k ≤ number of unique elements
• Any order allowed for ties
• k ≥ 1
• k ≤ number of unique elements
• Any order allowed for ties
Concept Explanation
We count how many times each number appears,
then pick the k numbers with the highest counts.
then pick the k numbers with the highest counts.
Step-by-Step Explanation
1.Read n and the array elements.
2.Read k.
3.Create a HashMap to store frequency of each number.
4.Traverse the array and update frequency in the map.
5.Create a min-heap (PriorityQueue) of size k
• Heap stores numbers
• Compare based on frequency (smallest frequency at top).
6.For each number in the map:
• Add number to heap.
• If heap size becomes greater than k, remove the top element.
7.Elements left in heap are the k most frequent numbers.
8.Return or print these numbers as a list.
2.Read k.
3.Create a HashMap to store frequency of each number.
4.Traverse the array and update frequency in the map.
5.Create a min-heap (PriorityQueue) of size k
• Heap stores numbers
• Compare based on frequency (smallest frequency at top).
6.For each number in the map:
• Add number to heap.
• If heap size becomes greater than k, remove the top element.
7.Elements left in heap are the k most frequent numbers.
8.Return or print these numbers as a list.
Concept Explanation
We count how many times each number appears,
then pick the k numbers with the highest counts.
then pick the k numbers with the highest counts.
Step-by-Step Explanation
1.Read n and the array elements.
2.Read k.
3.Create a HashMap to store frequency of each number.
4.Traverse the array and update frequency in the map.
5.Create a min-heap (PriorityQueue) of size k
• Heap stores numbers
• Compare based on frequency (smallest frequency at top).
6.For each number in the map:
• Add number to heap.
• If heap size becomes greater than k, remove the top element.
7.Elements left in heap are the k most frequent numbers.
8.Return or print these numbers as a list.
2.Read k.
3.Create a HashMap to store frequency of each number.
4.Traverse the array and update frequency in the map.
5.Create a min-heap (PriorityQueue) of size k
• Heap stores numbers
• Compare based on frequency (smallest frequency at top).
6.For each number in the map:
• Add number to heap.
• If heap size becomes greater than k, remove the top element.
7.Elements left in heap are the k most frequent numbers.
8.Return or print these numbers as a list.
Input / Output Format
Input Format
An integer n (size of array)
Then n integers (array elements)
An integer k
Then n integers (array elements)
An integer k
Output Format
k numbers with the highest frequency.
(Any order is acceptable if frequencies are same)
(Any order is acceptable if frequencies are same)
Constraints
• n ≥ 1
• k ≥ 1
• k ≤ number of unique elements
• Any order allowed for ties
• k ≥ 1
• k ≤ number of unique elements
• Any order allowed for ties
Examples
Input:
8
1 1 1 2 2 3 3 4
2
Output:
[1, 2]
Example Solution (Public)
static int[] topK(int[] a,int k){java.util.HashMap<Integer,Integer> m=new java.util.HashMap<>();for(int x:a) m.put(x,m.getOrDefault(x,0)+1);java.util.PriorityQueue<int[]> pq=new java.util.PriorityQueue<>((u,v)->Integer.compare(u[1],v[1]));for(java.util.Map.Entry<Integer,Integer> e:m.entrySet()){pq.add(new int[]{e.getKey(),e.getValue()});if(pq.size()>k) pq.poll();}int[] res=new int[pq.size()];for(int i=res.length-1;i>=0;i--) res[i]=pq.poll()[0];return res;}
Official Solution Code
static int[] topK(int[] a,int k){java.util.HashMap<Integer,Integer> m=new java.util.HashMap<>();for(int x:a) m.put(x,m.getOrDefault(x,0)+1);java.util.PriorityQueue<int[]> pq=new java.util.PriorityQueue<>((u,v)->Integer.compare(u[1],v[1]));for(java.util.Map.Entry<Integer,Integer> e:m.entrySet()){pq.add(new int[]{e.getKey(),e.getValue()});if(pq.size()>k) pq.poll();}int[] res=new int[pq.size()];for(int i=res.length-1;i>=0;i--) res[i]=pq.poll()[0];return res;}
Please login to submit solutions.