Why my code TLE, and what's the time complexity of my code?


  • 0
    1
    class Solution {
    
    public:
        int longestConsecutive(vector<int>& nums) {
            int length = nums.size();
            if(length == 0)
                return 0;
            unordered_map<int, int> imap;
            for(int i = 0; i < length; i++)
                if(imap.count(nums[i]) == 0)
                    imap.insert(make_pair(nums[i], i));
            vector<bool> visited(length, false);
            int result = 0;
            
            for(int i = 0; i < length; i++) {
                if(!visited[i]) {
                    int count = 1;
                    visited[i] = true;
                    int j = i;
                    
                    while(imap.find(nums[j]-1) != imap.end()) {
                        j = imap[nums[j]-1];
                        visited[j] = true;
                        count++;
                    }
                    
                    j = i;
                    while(imap.find(nums[j]+1) != imap.end()) {
                        j = imap[nums[j]+1];
                        visited[j] = true;
                        count++;
                    }
                    result = max(result, count);
                 }
            }
            return result;
        }
    };

  • 1
    R

    Make this change:

        vector<bool> visited(length, false);
        for(int i = 0; i < length; i++)
            if(imap.count(nums[i]) == 0) 
                imap.insert(make_pair(nums[i], i));
            else visited[i] = true;
    

    The thing is you started your DFS from the numbers you haven't put into the imap, thus doing some unnecessary work. On my computer the fix above allowed to shrink CPU time from 0.359 sec to 0.002. Also you don't need to store the indexes, the only thing you need are the numbers themselves. That way you could improve running time as well.

    As for the time complexity, your code is O(n) on average, although the constant is quite big. My best O(n) on average solution turned out to be slower than just sorting the vector and iterating once over it (O(n*lg(n)). So even though the time complexity asked for was linear, I would suggest the linearithmic solution as a better one.


  • 0
    1

    Thank you so much!


Log in to reply
 

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