Most frequent numbers

Medium

2000 ms limit256 MB memoryHash maps Heaps Sorting Arrays

Stuck?

Show a hint

Count how many times each number appears, then order those counts and take the first k. Ties go to the smaller number.

The ideas behind this problem

Heaps: when you only ever want the next one Trading memory for time with a hash map

Next in this lesson

Merging many sorted lists at once

Given a list of numbers and a value k, return the k numbers that appear most often, in decreasing order of how often they appear. Where two numbers appear equally often, the smaller number comes first.

Worked example#

For [1, 1, 1, 2, 2, 3] with k = 2, count first:

number	times
1	3
2	2
3	1

Sorted by count, highest first: 1, then 2, then 3. Taking the first two gives [1, 2].

Two steps: count, then take the largest counts. Counting is a hash map. Taking the largest few can be a sort, or a heap when k is much smaller than the number of distinct values.

Constraints#

1 <= n <= 100000
1 <= k <= number of distinct values

Input

nums is a count then that many integers. k is one integer.

Output

The k most frequent numbers, separated by spaces.

Examples

Input

6
1 1 1 2 2 3
2

Output

1 2

1 appears three times and 2 appears twice, so those are the top two.

Input

1
1
1

Output

One number, one answer.

Input

5
3 3 1 1 2
2

Output

1 3

1 and 3 both appear twice, so the smaller one comes first.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.