Can the problem be solved in O(n) time?


  • 0
    C

    I think maybe the problem cannot be solved in O(n) time. Think about the extreme case where there are either only two consecutive numbers or no consecutive numbers at all. To distinguish between these two cases, we need to query all the previous numbers for every new number. But this query cannot be done in constant time. So this problem, overall, cannot be solved in O(n) time. Is this reasonable?

    Thanks.


  • 5
    B

    Well, below is a O(n) time and O(n) space solution. To outline the algorithm, first put all the elements into a map. The make a second pass over the input and for each element (that still exists in the map), erase the number and its neighboring numbers, and in the process count the length of consecutive sequence.

    class Solution {
    public:
        int longestConsecutive(vector<int> &num) {
            unordered_set<int> map;
            
            for (unsigned i = 0; i < num.size(); ++i) {
                map.insert(num[i]);
            }
            
            int longest = 0;
            for (unsigned i = 0; i < num.size(); ++i) {
                if (map.find(num[i]) == map.end()) continue;
                
                map.erase(num[i]);
                int subSeq = 1;
                
                int n = num[i] - 1;
                while ((map.find(n) != map.end())) {
                    ++subSeq;
                    map.erase(n--);
                }
                
                n = num[i] + 1;
                while (map.find(n) != map.end()) {
                    ++subSeq;
                    map.erase(n++);
                }
                
                longest = (subSeq > longest) ? subSeq : longest;
            }
            
            return longest;
        }
    };

  • 0
    M

    Hello, I think std::map is based on RBTre, the complexity of a query is O(log N), so the complexity of the algorithm is O( Nlog(N) ).


  • 0
    X

    the answer uses unordered_set(hash_set), so its O(n). but the variable name is confusing.


  • 0
    V

    What's your run time?
    My solution is 52ms


Log in to reply
 

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