Most Popular Integers Google Python Interview Question

Given an integer array and an integer as input, return the top integers in the array (the ones that appear most frequently). Return the output in non-decreasing order. The test cases are generated in such a way that there will be a unique answer.

Example #1

Input:

Output:

Explanation: The most frequent elements are: with a frequency of , with a frequency of , and with a frequency of . Finally, the output is sorted in non-decreasing order.

Example #2

Input:

Output:

Sorting Approach

The first step in solving this problem is to count the frequency of each number using a dictionary.
Next, we need to sort the numbers based on their frequencies so that the most frequent numbers appear first.

If we sort only the frequencies, we will lose track of the actual numbers. To avoid this, we store each number along with its frequency as a pair (frequency, number) inside a list. Each element in this list will be another list of size , where:

• The first value represents the frequency.
• The second value is the actual number.

Now, we sort this list. When sorting a list of lists, Python sorts based on the first element by default. Since we stored frequency first, numbers with lower frequencies will appear first.
To get the most frequent numbers first, we set in the function.

Finally, we take the first elements from this sorted list and extract only the second value (the actual number).

Here's the code to do that:

Optimized Sorting Approach

Intuition

Instead of sorting, what if we group numbers based on their frequency?
We can do this in two ways:

1. Using a dictionary: The key is the frequency, and the value is a list of numbers with that frequency.
2. Using a list: The index represents the frequency, and the value at that index is a list of numbers with that frequency.

Let’s analyze the second approach(using a list):

• After building the list, numbers with the highest frequency will appear at the last indices, while numbers with lower frequencies will appear earlier.
• Some indices may be empty if no numbers have that frequency.
• Since the elements are already arranged by increasing frequency (left to right), we don’t need to sort manually.

Implementation Steps

1. Count the frequency of each number using a dictionary.
2. Create a list of size equal to , where each index represents a frequency.
3. Place each number in the list at the index equal to its frequency.
4. Start from the last index, collect numbers into the result list, and stop when we have numbers.

Here's the code to do that: