19 Sep 2023, 3:24 PM
19 Sep 2023, 3:24 PM

8. Longest Consecutive Sequence

#leetcode/128

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

Solution

Solution in C++ using sort

The most straightforward approach that comes to mind involves first sorting the array. Then, by iterating over it, we can check if nums[i] + 1 == nums[i + 1]. If true, it indicates a potential sequence; otherwise, the sequence concludes, and at this point, we can check if it's the longest sequence found so far. Finally, it's important to note that a sequence of identical numbers does not interrupt the continuity of the sequence (this is the reason of if(nums[i] != nums[i + 1])).

int longestConsecutive(vector<int>& nums) {
	if(nums.size() == 0) return 0;
	sort(nums.begin(), nums.end());
	int seqCount = 1, maxSeq = 1;

	for(int i = 0; i < nums.size() - 1; i++) {
		/* a sequence of identical numbers does not interrupt the continuity of the sequence */
		if(nums[i] != nums[i + 1]) {
			//a potential sequence is starting
			if(nums[i] + 1 == nums[i + 1])
				seqCount++;
			//the sequence concludes
			else if (nums[i] + 1 != nums[i + 1]) {
				//maybe it's the longest sequence found so far
				maxSeq = max(seqCount, maxSeq);
				//we restart the sequence counter
				seqCount = 1;
			}
		}
	}
	return max(seqCount, maxSeq);
}

Solution in C++ using hash map

After all, the trick is to find where the sequence begins. Once we've got that, we can keep adding 1 until we hit the sequence's end. Once we're there, we figure out how long the sequence is and see if it's the longest one we've found yet. We can do this using a hash map. Since we see the whole array always 3 times, the time complexity is O(n).

int longestConsecutive(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        
        unordered_map<int, bool> map;

		//initially, all numbers can be the start of the sequence
        for(int num : nums)
            map[num] = true;

		/*for every number in nums, if num - 1 is present, num can't be the start of the sequence */
        for(auto pair : map) {
            int num = pair.first;
            if(map.find(num - 1) != map.end())
                map[num] = false;
        }
        // now the start of each sequence is true
        int seqCount = 1, maxSeq = 1;
        for(auto pair : map) {
            int num = pair.first;
            //if the start of a sequence is found
            if(pair.second == true) {
	            //keep adding 1 until we hit the sequence's end
                while(map.find(num + 1) != map.end()) {
                    seqCount++;
                    num++;
                }
                //maybe it's the longest sequence found so far
                maxSeq = max(maxSeq, seqCount);
                seqCount = 1;
            }
        }

        return maxSeq;
    }