Top K Frequent Elements

Top K Frequent Elements

Hard Python Lists 12 views
Explanation Complexity

Problem Statement

Read n integers and k. Output k elements with highest frequency. If tie, smaller number first. Output in order of frequency desc then number asc.

Input Format

First line n k. Second line n integers.

Output Format

One line of k numbers.

Example

8 2
1 1 1 2 2 3 3 3
1 3

Constraints

1

Input / Output Format

Input Format
First line n k. Second line n integers.
Output Format
One line of k numbers.
Constraints
1

Examples

Input:
8 2 1 1 1 2 2 3 3 3
Output:
1 3

Example Solution (Public)

Python 
import sys,heapq
p=sys.stdin.read().strip().split()
if len(p)<2: sys.exit(0)
n=int(p[0]); k=int(p[1])
a=list(map(int,p[2:2+n]))
mp={}
for v in a:
  mp[v]=mp.get(v,0)+1
heap=[]
for v,c in mp.items():
  heapq.heappush(heap,(-c,v))
out=[]
for _ in range(min(k,len(heap))):
  c,v=heapq.heappop(heap)
  out.append(str(v))
sys.stdout.write(' '.join(out))

Official Solution Code

import sys,heapq
p=sys.stdin.read().strip().split()
if len(p)<2: sys.exit(0)
n=int(p[0]); k=int(p[1])
a=list(map(int,p[2:2+n]))
mp={}
for v in a:
  mp[v]=mp.get(v,0)+1
heap=[]
for v,c in mp.items():
  heapq.heappush(heap,(-c,v))
out=[]
for _ in range(min(k,len(heap))):
  c,v=heapq.heappop(heap)
  out.append(str(v))
sys.stdout.write(' '.join(out))
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.