128. Longest Consecutive Subsequence

Prompt

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.

Examples

• 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
• Example 3:
  • Input: nums = [1,0,1,2]
  • Output: 3

Solutions

Set Solution

In C++

int longestConsecutive(vector<int>& nums) {
	if (nums.empty()) return 0;
 
	unordered_set<int> set;
	set.reserve(nums.size());
	set.insert(nums.begin(), nums.end());
 
	int answer = 1;
	for (int num : set) {
		if (!set.contains(num - 1)) {
			int maxlen = 1;
			while (set.contains(num + maxlen)) maxlen++;
			answer = max(maxlen, answer);
		}
	}
 
	return answer;
}

Explanation

Foreach unique element that is the beginning of a sequence, see long the sequence after it is, and if it is longer than the current max, update the max to reflect that. We can unique elements by creating a set from the input list. We determine the beginning of a sequence by checking if a the set has the predeccessor of the given number.

We reserve the size of the set in order to handle really big inputs efficiently.

Big O Analysis

Time Complexity

The time complexity is $O(n)$.

Auxiliary Space Complexity

The space complexity is $O(n)$.