Java O(n) Easy To Understand, Optimal Solution

• Explanation
The idea to this question is to use Bucket Sort, taking advantage of the fact that the minimum and maximum frequencies an element in nums can occur are 0 and nums.length, respectively.

1. Construct a dictionary, that maps each distinct element to it's frequency in nums.
2. Create an array of lists, freqs, with size n+1. The index of a list in freqs is very informative. Suppose freqs[4] = { 1, 2, 3 }. This means elements 1, 2, 3 occur 4 times each in nums. Populate freqs with data from the dictionary in step 1).
3. Retrieve the top k elements starting from index n in freqs.

Time Complexity
The time complexity is O(n) where n is the number of elements in nums, since steps 1, 2, 3 all run in O(n) time.

class Solution {
// Retrieves up to n number of elements from list elements
public List<Integer> getElements(List<Integer> elements, int n) {
List<Integer> result = new ArrayList<>();
if (elements == null || n == 0) {
return result;
}
// Keep appending to our result up until n elements is reached
for (int i = 0; i < elements.size(); i++) {
if (result.size() == n) {
break;
}
}
return result;
}

public List<Integer> topKFrequent(int[] nums, int k) {
// 1. Map elements to their frequencies in nums
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
Integer count = map.get(num);
if (count == null) {
map.put(num, 1);
} else {
map.put(num, count + 1);
}
}
// Frequency can range from 0 to n
ArrayList<Integer> [] freqs = new ArrayList[nums.length + 1];

// 2. Populate our freqs array of ArrayLists
for (Integer key : map.keySet()) {
int frequency = map.get(key);
if (freqs[frequency] == null) {
freqs[frequency] = new ArrayList<>();
}
}
// 3. Retrieve the top k elements from out freqs array
List<Integer> result = new ArrayList<>();
int index = nums.length;
while (result.size() != k && index >= 0) {
List<Integer> elements = freqs[index];
if (elements != null) {