Leetcode - Top K Elements in List

Question

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Must be faster than O(n*log(n))

This is anarrays question.

Idea
Brute Force:

• If I Iterate through the list and keep count of how often each number appears, I can do that in O(n) time
• Sorting the hashmap will take O(n*log(n)) time
• Returning the top k keys in the hashmap will take O(k) Instead of mapping numbers to counts, can we flip it and map counts to numbers?

Solution