347. Top K Frequent Elements

📝 Problem Details

• Title: 347. Top K Frequent Elements
• Link: https://leetcode.com/problems/top-k-frequent-elements/
• Difficulty: Medium
• Tags/Categories: Hashmap Arrays Bucket-Sort

input array nums input integer k return k most frequent elements

💭What Were My Initial Thoughts?

Constraint: algorithm must be better than O(n log n)
	- this rules out any sorting of sort-based data structure (heap)
	- otherwise, a brute-force approach would involve counting occurrences, sorting by frequency, and picking the top `k` elements.

💡 Explanation of Solution

- use a hashmap : traverse the array to build a frequency map of each element 

- use bucket sort 
	- init a 2d vector called buckets of size n+1
	- each index in the array represents elements that share the same frequency
	- place each number into the corresponding bucket basd on its frequency

- retrieve the top k elements
	- init a results vector
	- start from the back of the buckets array and work backward
	- push elements into the results vector until we have reached size k

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        int n = nums.size();
 
        for(int i=0; i < n; i++) {
            if(map.find(nums[i]) != map.end()) {
                map[nums[i]]++;
            } else {
                map[nums[i]] = 1;
            }
        }
 
        vector<vector<int>> buckets(n+1);
        for(auto it = map.begin(); it != map.end(); it++) {
            buckets[it->second].push_back(it->first);
        }
 
        vector<int> result;
 
        for(int i = buckets.size()-1; i >= 0; i--) {
            if(result.size() == k) break;
            result.insert(result.begin(), buckets[i].begin(), buckets[i].end());
        }
 
        return result;
    }
};