Is my solution O(n)? If it is, why it is so slow. BTW I didn't similar solution here.

  • 0

    Idea is simple, just put the number to their times they appear. For example. log[0] stores all the number that appear once. log[3] stores all number that appear 4 times etc. The maximum times of an element could've appeared is n times where n is size of the array. I put time complexity analysis on each function. This should be O(n). Please correct me if I'm wrong

    class Solution {
        vector<int> topKFrequent(vector<int>& nums, int k) {
            vector<list<int>> log (nums.size(), list<int>());
            unordered_map<int, int> counter;
            unordered_map<int, list<int>::iterator> pointer;
            for (int i = 0; i < nums.size(); i++) {
                int current = nums[i];
                if (counter[current]) {
                    int previousCount = counter[current];
                    log[previousCount-1].erase(pointer[current]);   //O(1)
                    counter[current] ++;
                    log[previousCount].insert(log[previousCount].begin(), current);     //O(1)
                    pointer[current] = log[previousCount].begin();
                else {
                    counter[current] = 1;
                    log[0].insert(log[0].begin(), current);     //O(1)
                    pointer[current] = log[0].begin();
            vector<int> result;
            //O(k) while k is at most n:
            for (int i = nums.size()-1; i >= 0; i--) {
                if (result.size() >= k) {
                if (!log[i].empty()) {
                    for (int num : log[i]) {
            return result;

Log in to reply

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