DAY 4 #coding challenge

Problem Statement (Top k numbers in a stream: medium)

Given N numbers in an array, your task is to keep at most the top K numbers with respect to their frequency.

In other words, you have to iterate over the array, and after each index, determine the top K most frequent numbers until that iteration and store them in an array in decreasing order of frequency. An array will be formed for each iteration and stored in an array of arrays. If the total number of distinct elements is less than K, then keep all the distinct numbers in the array. If two numbers have equal frequency, place the smaller number first in the array.

Input:
N=5, K=4
arr[] = {5, 2, 1, 3, 2} 
Output: 
5 
2 5 
1 2 5 
1 2 3 5 
2 1 3 5 
Explanation:
Firstly there was 5 whose frequency
is max till now. So resulting sequence is {5}.
Then came 2, which is smaller than 5 but
their frequencies are same so resulting sequence is {2, 5}.
Then came 1, which is the smallest among all the
numbers arrived, so resulting sequence is {1, 2, 5}.
Then came 3 , so resulting sequence is {1, 2, 3, 5}
Then again 2, which has the highest
frequency among all numbers, 
so resulting sequence {2, 1, 3, 5}.

vector<vector<int>> kTop(vector<int>& a, int N, int K) {
        // code here
        vector<vector<int>> final_ans;
        vector<int> top(K + 1, 0);
        unordered_map<int, int> freq;

        for (int m = 0; m < N; ++m) {
            if (freq.find(a[m]) != freq.end()) {
                freq[a[m]] += 1;
            } else {
                freq[a[m]] = 1;
            }

            top[K] = a[m];
            int i = find(top.begin(), top.end(), a[m]) - top.begin() - 1;

            while (i >= 0) {
                if (freq[top[i]] < freq[top[i + 1]]) {
                    swap(top[i], top[i + 1]);
                } else if ((freq[top[i]] == freq[top[i + 1]]) && (top[i] > top[i + 1])) {
                    swap(top[i], top[i + 1]);
                } else {
                    break;
                }
                i -= 1;
            }

            i = 0;
            vector<int> ans;
            while (i < K && top[i] != 0) {
                ans.push_back(top[i]);
                i += 1;
            }

            final_ans.push_back(ans);
        }

        return final_ans;
    }

I walked as the outdoor activity.