3.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]

Solution: (Using Priority Queue and Hashmaps)

Algorithm :

1. Create a Hashmap , to store key-value pair, i.e. element-frequency pair.

2. Store the element-frequency pair in a Priority Queue and create the Priority Queue, this takes O(n) time.

3. Run a loop k times, and in each iteration remove the top of the priority queue and print the element.

class Solution
{
public:
    vector<int> topKFrequent(vector<int> &nums, int k)
    {
        unordered_map<int, int> m;
        vector<int> v;
        for (int i = 0; i < nums.size(); i++)
        {
            if (m.find(nums[i]) == m.end())
            {
                m.insert({nums[i], 1});
            }
            else
            {
                m[nums[i]]++;
            }
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>> pq;
        
        for(auto itr=m.begin();itr!=m.end();itr++){
            pq.push({itr->second,itr->first});
        }

        for (int i = 0; i < k; i++)
        {
            v.push_back(pq.top().second);
            pq.pop();
        }

        return v;
    }
};

Complexity Analysis:

• Time Complexity: O(k log d + d), where d is the count of distinct elements in the array. To remove the top of priority queue O(log d) time is required, so if k elements are removed then O(k log d) time is required and to traverse the distinct elements O(d) time is required.

• Auxiliary Space: O(n) for hashmaps

Solution: (Quick Select)

class Solution
{
public:
    int findPivot(vector<pair<int, int>> &v, int start, int end)
    {

        int pvt = end;
        int k = start;

        for (int i = start; i < end; i++)
        {
            if (v[i].second <= v[pvt].second)
            {
                swap(v[i], v[k]);
                k++;
            }
        }

        swap(v[k], v[pvt]);
        return k;
    }

    void quickSelect(vector<pair<int, int>> &v, int start, int end, int k)
    {
        if (start >= end)
        {
            return;
        }

        int p = findPivot(v, start, end);

        if (p == k)
        {
            return;
        }

        if (p < k)
        {
            quickSelect(v, p + 1, end, k);
        }
        else if (p > k)
        {
            quickSelect(v, start, p - 1, k);
        }

        return;
    }

    vector<int> topKFrequent(vector<int> &nums, int k)
    {
        unordered_map<int, int> m;
        vector<int> res;

        for (int i = 0; i < nums.size(); i++)
        {
            m[nums[i]]++;
        }

        vector<pair<int, int>> v;

        for (auto itr = m.begin(); itr != m.end(); itr++)
        {
            v.push_back({itr->first, itr->second});
        }

        int n = v.size();

        quickSelect(v, 0, n - 1, n - k);

        for (int i = n - k; i < n; i++)
        {
            res.push_back(v[i].first);
        }

        return res;
    }
};

Time Complexity: O(n)