Crash Code Part-5 (Top K Elements!)

Problem Description

You are given a list of integers nums. Your task is to find the k elements that occur most frequently in the list. Return exactly k integers sorted in ascending order. The catch? We want to do this efficiently without relying on overly complex nested loops, leveraging Java 8’s powerful Collections framework and lambda expressions instead. Everything needs to happen cleanly inside the main method.

Constraints

• 1 <= n <= 10000
• -1000 <= nums[i] <= 1000
• 1 <= k <= n

Input

• The first line contains an integer n, the number of elements in the list.
• The next n lines each contain an integer representing the elements of nums.
• The last line contains an integer k.

Output

Return the k most frequent elements as a List<Integer>, sorted in ascending order. (Note: the driver code handles printing).

Examples

Example

Input:

6
1
2
2
3
3
3
2

Output:

2
3

Explanation:

n = 6, meaning there are 6 elements in the list.
The list nums is: [1, 2, 2, 3, 3, 3].
k = 2, meaning we need the 2 most frequent numbers.

Now, count the frequency of each number:
* 1 -> occurs 1 time
* 2 -> occurs 2 times
* 3 -> occurs 3 times

The top 2 elements with the highest frequency are 3 (3 times) and 2 (2 times).
After sorting them in ascending order, we get:
[2, 3].

The Concepts Under the Hood

Instead of manually counting and tracking highest counts with multiple nested arrays (which gets messy and scales poorly), we can use a combination of a Hash Map and Custom Sorting. It relies on a neat logical trick using simple steps to achieve a clean solution:

1. The Hash Map Math: We iterate through the array once and store the frequency of each number using a Hash Map (Map<Integer, Integer>). We utilize Java 8’s getOrDefault to seamlessly initialize or increment our frequency counts.
2. Isolate Unique Elements: We grab only the unique keys (the distinct numbers) from our map and place them into a new list.
3. Custom Sort by Frequency: We sort this list of unique numbers. Instead of sorting by their natural value, we provide a custom Java 8 lambda comparator to sort them based on their frequency (the values from our map) in descending order.
4. Sublist and Final Sort: We slice out the first k elements from our newly sorted list, which represent our top frequent numbers. Finally, because the constraints strictly dictate an ascending output, we sort this specific sublist one last time in natural ascending order.

Visualizing the Frequency Map and Sort

Since we want to rely on standard Java utilities rather than external helper methods, we execute a custom comparator sort directly inline. Here is how the mapping and sorting technique looks in action for the list [1, 2, 2, 3, 3, 3].

Step 1: Building the Map

We process each number, mapping the element (Key) to its occurrence count (Value).

Number (Key) -> Frequency (Value)
1            -> 1
2            -> 2
3            -> 3

Step 2: Extract Keys and Custom Sort

We pull the unique keys into a list: [1, 2, 3]. Next, we sort this list by comparing the Values from the map, pushing the highest frequencies to the front.

• Compare 1 and 2: freq(2) is 2, freq(1) is 1. Number 2 moves ahead.
• Compare 2 and 3: freq(3) is 3, freq(2) is 2. Number 3 moves ahead.

Sorted Unique List:

[ 3, 2, 1 ]

Step 3: Extract Top K and Final Sort

We need k = 2 elements, so we take a sublist from index 0 to 2. Sublist: [3, 2]

We perform a final ascending sort to satisfy the output requirements: Final Output: [2, 3]

Solve

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.io.*;
import java.util.*;

class Result {
    public static List topKFrequent(List nums, int k) {
        // 1. Map to store frequency of each number
        Map <Integer, Integer> freqMap = new HashMap < > ();
        for (int num: nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // 2. Extract unique keys into a list
        List <Integer> uniqueNums = new ArrayList < > (freqMap.keySet());

        // 3. Custom sort the keys by frequency descending
        uniqueNums.sort((a, b) - > {
            int freqCompare = freqMap.get(b).compareTo(freqMap.get(a));
            if (freqCompare == 0) {
                return a.compareTo(b);
            }
            return freqCompare;
        });

        // 4. Extract top k elements
        List <Integer> result = new ArrayList <> (uniqueNums.subList(0, Math.min(k, uniqueNums.size())));

        // 5. Final sort in ascending order
        Collections.sort(result);

        return result;
    }

}