Possibly shortest cpp solution, only 6 lines.


  • 97

    use a hash map to store boundary information of consecutive sequence for each element; there 4 cases when a new element i reached:

    1. neither i+1 nor i-1 has been seen: m[i]=1;

    2. both i+1 and i-1 have been seen: extend m[i+m[i+1]] and m[i-m[i-1]] to each other;

    3. only i+1 has been seen: extend m[i+m[i+1]] and m[i] to each other;

    4. only i-1 has been seen: extend m[i-m[i-1]] and m[i] to each other.

    int longestConsecutive(vector<int> &num) {
    	unordered_map<int, int> m;
    	int r = 0;
    	for (int i : num) {
    		if (m[i]) continue;
    		r = max(r, m[i] = m[i + m[i + 1]] = m[i - m[i - 1]] = m[i + 1] + m[i - 1] + 1);
    	}
    	return r;
    }

  • 0
    J

    How do you know the second value in the pair must be initialized with a 0?


  • 0

  • 2
    J

    Thanks. It seems that the default allocator will use new int() to default-ininitialize it to 0, according to C++ ISO standard 14882:2003. Chapter 8.5, Clause-5,7:

    To zero-initialize an object of type T means:

    • if T is a scalar type (3.9), the object is set to the value of 0 (zero) converted to T;

    To value-initialize an object of type T means:

    • if T is a class type (clause 9) with a user-declared constructor (12.1), then the default constructor for T is called (and the initialization is ill-formed if T has no accessible default constructor);

    • if T is a non-union class type without a user-declared constructor, then every non-static data member and base-class component of T is value-initialized;

    • if T is an array type, then each element is value-initialized;

    • otherwise, the object is zero-initialized

    To default-initialize an object of type T means:

    • if T is a non-POD class type (clause 9), the default constructor for T is called (and the initialization is ill-formed if T has no accessible default constructor);

    • if T is an array type, each element is default-initialized;

    • otherwise, the object is zero-initialized.

    An object whose initializer is an empty set of parentheses, i.e., (), shall be value-initialized.

    There are also similar rules in C++11 ISO Standard draft.


  • 0
    X

    I ran into this really weird bug. So basically I changed one line of your code: to check duplicate, I changed if(m[i]) continue; to if(m.count(i)) continue. After the change the code no longer works. It fails on input [0,-1] and gives an output of 1, which is wrong. Any thoughts?

    int longestConsecutive(vector<int> &num) {

    unordered_map<int, int> m;
    
    int r = 0;
    
    for (int i : num) {
    
        if (m.count(i)) continue;
    
        r = max(r, m[i] = m[i + m[i + 1]] = m[i - m[i - 1]] = m[i + 1] + m[i - 1] + 1);
    
    }
    
    return r;
    

    }


  • 0
    J

    Hi, xiaoxiaoEx. It should skip only if m[i] > 0, not if m[i] existed.


  • 0
    M

    @jakwings: Just a quick question, in what case would m[i] exists but !(m[i] > 0)?


  • 0
    J

    @melvin.ming.gong If you are getting a value from the map with a new key, then it will insert an default-constructed value into the map. If m[1+1] doesn't exist, it will be 0.


  • 0
    M

    Thanks jakwings~


  • 43
    R

    Great code, I think this is the one of the best among the solutions of all the problems in terms of thinking and optimizing.
    You may wonder what the code means and here's the same idea with more lines, just to make the logic clearer.

    As you can see, the code below can be reduced by merging the if statements, finally you will get the code in the above solution. Hope my walkthrough can be helpful.

    int longestConsecutive(vector<int> num) {
        unordered_map<int,int> m;
        int ret = 0;
        for(auto & n: num){
    
            //it is in the middle of some consecutive sequence OR we can say it is already visited earlier
            //therefore it does not contribute to a longer sequence
            if(m[n]) continue; 
    
            //we cannot find adjacent sequences to n, therefore it is a single element sequence by itself
            if(m.find(n-1) == m.end() && m.find(n+1) == m.end()){ // 
                ret = max(ret, m[n] = 1);
                continue;
            }
    
            //found a sequence at n+1
            //you may wonder what if the sequence at n+1 contains element n?
            //It it contains n, when we add the length by 1 using m[n+1]+1, it is wrong, right?
            //However it is not possible, because if sequence at n+1 contains n, m[n] must have been visited earlier
            //we checked that using if(m[n]) continue; here m[n] is not yet visited;
            //therefore sequence m[n+1] is always on right side, we can safely extend the length by 1
            if(m.find(n-1)==m.end()){ 
                
                //we want to maintain the TWO boundaries of the sequence
                //the new length of the sequence is the original length m[n+1] incremented by 1
                //left boundary m[n] = m[n+1] +1;
                //right boundary m[n+m[n+1]] = m[n+1]+1;
                //why n+m[n+1]? it is equal to m[n+1]+(n+1)-1 
                //meaning the old left boundary n+1 plus the old length m[n+1] minus 1
                //e.g. for sequence 3,4,5,6 m[3] = 4, and right boundary 6 = 3+m[3]-1 (here n+1 == 3);
                int r = m[n] = m[n+m[n+1]] = m[n+1]+1;
                ret = max(ret, r);
                continue;
            }
            
            //this is similar to the above case just extend to the right
            if(m.find(n+1)==m.end()){
                int r = m[n] = m[n-m[n-1]] = m[n-1]+1;
                ret = max(ret,r);
                continue;
            }
            
            //here, we found both sequences at n+1 and n-1, for reasons we explained,
            //the sequences have no overlap.
            //Now, we just need to add the length of current element n (which is 1) to both left and right boundaries
            //the new length will be :  
            //old length of left sequence (m[n-1]) + old length of right sequence (m[n+1]) + 1
            //We also need to mark m[n] as visited, here we can either mark it with 1 or the new length;
            int r = m[n-m[n-1]] = m[n+m[n+1]] = 1+ m[n+1]+ m[n-1];
            m[n] = 1; //basically we just need to mark m[n] as any non-zero number
            // or we can write
            //int r = m[n] = m[n-m[n-1]] = m[n+m[n+1]] = 1+ m[n+1]+ m[n-1];
            ret = max(ret,r);
        }
        return ret;

  • 0
    R

    very helpful comments, thanks :)


  • 0
    L

    Thanks a lot for your comments. :)


  • 0
    A

    thanks a lot, what a wonderful idea!!


  • 0
    A

    the use of auto &n:num is really great!!


  • 1
    H

    thanks a lot, you did a great job explaining it


  • 0
    P

    very smart idea!!!


  • 0

    Damn clever idea!!! Thanks for your sharing.


  • 0
    V

    I think that it would be something wrong if num[i] is equal to INT_ MIN or INT_ MAX?


  • 0
    7

    wonderful ideal


  • 0

    @rellik Nice comment. However if you use find() it'd introduce logN complexity, making the overall complexity O(NlogN). So one still need mzchen's initialization to 0 trick to achieve O(N).


Log in to reply
 

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