> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/hashmap-and-hashset-and-sliding-window/top-k-frequent-elements.md).

# Top K Frequent Elements

Given a non-empty array of integers, return the **k** most frequent elements.

**Example 1:**

```
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
```

**Example 2:**

```
Input: nums = [1], k = 1
Output: [1]
```

**Note:**

* You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
* Your algorithm's time complexity **must be** better than O(n log n), where n is the array's size.
* It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
* You can return the answer in any order.

```java
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums)
            map.put(x, map.getOrDefault(x, 0) + 1);
        ArrayList<Integer>[] list = new ArrayList[nums.length + 1];
        for (int x : map.keySet()) {
            if (list[map.get(x)] == null)
                list[map.get(x)] = new ArrayList<>();
            list[map.get(x)].add(x);
        }
        int[] ans = new int[k];
        int index = 0;
        for (int i = list.length - 1; i >= 0 && k > 0; i--) {
            if (list[i] != null) {
                for (int j = 0; k > 0 && j < list[i].size(); j++) {
                    ans[index++] = list[i].get(j);
                    k--;
                }
                if (k == 0)
                    break;
            }
        }
        return ans;
    }
}
```