# My O(n) solution

• Here are the steps of my solution:

1-Calculate the frequency of each number using hashmap. O(N)

2-For each frequency value, store the numbers with this frequency O(N).

3-Loop from frequency n to 1 and take the first K numbers. O(N+K)

The total complexity is O(N+K) which is O(N).

My code :

``````class Solution { public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> freq;
unordered_map<int,vector<int>> m;
for(int i=0;i<nums.size();i++)
{
freq[nums[i]]++;
}
for(auto itr=freq.begin();itr!=freq.end();itr++)
{
m[itr->second].push_back(itr->first);
}

vector <int> res;
for(int i=nums.size();i>=1 && k;i--)
{
if(!m.count(i)) continue;
for(int j=0;j<m[i].size()&&k;j++)
{
res.push_back(m[i][j]);
k--;
}
}
return res;
} };``````

• This post is deleted!

• This post is deleted!

• @Oleksii-Danylevskyi It's pretty obvious and nothing unusual. In the whole run, the total number of inner loop iterations is at most k. Either look at how k is handled, or realize that each iteration pushes one number into the result and that the result ends up with at most k numbers.

• @StefanPochmann Agree;)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.