Longest Consecutive Sequence (#128 Leetcode)

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

 

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

 

Method 1: 

If we sort the array, it would be O(n log n). Later, it would be easy. 

Method 2:

The problem is to find the longest consecutive sequence. Let's do one by one. 

1. Firstly, find the number to begin the sequence. If the number doesn't have any previous number, then it will be the start of the sequence. Sequence has been identified.

2. To find the consecutive sequence, now we need to find the consecutive number exists in the given vector. 

3. To find the longest consecutive sequence, we need to keep track of the counter. 

To do the above method, we need to search in vector every time. To search in vector, it is O(n). Instead of vector, if we store all the elements in the map or set, it would be just O(1). 

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int maxLen = 0, curNum = 0;
        int longSeq = 0;
        unordered_set<int> uos;
        
        for (int num : nums) {
            uos.insert(num);
        }
        /* 
         // Run through set elements. 
        for (int num: uos) {
            cout << num << " ";
        }
        */
        for (int num: nums) {
            if (uos.find(num-1) != uos.end()) {
                // If lesser number exists, num is 
                // not the start of the sequence.
                continue;
            }
            longSeq++;
            curNum = num + 1;
            
            /* If a consecutive number exists for num, 
               keep checking the next consecutive numbers. */
            while(uos.find(curNum) != uos.end()) {

                longSeq++;  
                curNum = curNum + 1;
            }
        
            maxLen = max(maxLen, longSeq);
            longSeq = 0;
        }
        
        return maxLen;
    }
};