~/leetcode $ 347. Top-K-Frequent-Elements

For this question, we can keep track of the frequency of each element and then sort the element by this frequency. This feels kind of brute force-y but it will still run in O(n log n) time as we linearly go through and count the frequency (O(n)) and then sort these frequencies (O(n log n).

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> count {};
        for (int num: nums) {
            if (count.contains(num)) {
                ++count[num];
            } else {
                count[num] = 1;
            }
        }

        vector<pair<int, int>> sorted {};
        for (pair<int, int> tmp: count) {
            sorted.push_back({tmp.second, tmp.first});
        }
        sort(sorted.begin(), sorted.end());
        vector<pair<int, int>> slicedSorted(sorted.end() - k, sorted.end());

        vector<int> result {};
        for (pair<int, int> e: slicedSorted) {
            result.push_back(e.second);
        }
        return result;
    }
}

Time Complexity: O(n log n)

Space Complexity: O(n)

Time Taken: 5m 58s