Longest Consecutive Sequence

Problem

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

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

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Sorting

Intuition

One approach is to sort the array first and then identify the longest subarray consisting of consecutive elements. This solution has a time complexity of O(n log n).

When we think of a "consecutive sequence," we naturally imagine numbers placed in order, like 1, 2, 3, 4. If the input array is jumbled, the most logical first step is to sort it. Once sorted, any consecutive numbers will be sitting right next to each other, making them easy to spot and count.

Approach

Sort the input array in ascending order.
Iterate through the sorted array.
Check the difference between the current number and the previous number:
- If the difference is 1, they are consecutive. Increment the current sequence length.
- If the difference is 0, they are duplicates. Ignore and move on.
- If the difference is greater than 1, the sequence is broken. Reset the current sequence length to 1.

Method 2 - Using Hashset

We can utilize a HashSet for adding and removing elements. Initially, all elements are added to the set. As we iterate through the array, we remove each element and count the consecutive elements smaller and larger than the current element.

When a new element n is inserted into the map, perform the following steps:

Check if n - 1 and n + 1 exist in the map. If they do, it indicates an existing sequence adjacent to n. The variables left and right will represent the lengths of these sequences, where 0 signifies no existing sequence, making n a boundary point. Store (left + right + 1) as the value associated with the key n in the map.
Utilize left and right to identify the other ends of the sequences to the left and right of n, and update the values with the new length.

Each time, update the maximum value accordingly.

Code

Java

public static int longestConsecutive(int[] nums) {
	if (nums == null || nums.length == 0) {
		return 0;
	}

	Set<Integer> set = Arrays.stream(nums).boxed()
						.collect(Collectors.toSet());
	int max = 1;

	for (int num : nums) {
		int left = num - 1;
		int right = num + 1;
		int count = 1;

		while (set.contains(left)) {
			count++;
			set.remove(left);
			left--;
		}

		while (set.contains(right)) {
			count++;
			set.remove(right);
			right++;
		}

		max = Math.max(count, max);
	}

	return max;
}

More concise code

Also, set.remove() returns boolean, which is true when element is removed, else no. So, we can get rid of set.contains(). Also, count is useless, as difference between max and min element in sequence will give us count.

public int longestConsecutive(int[] nums) {
	if (nums == null || nums.length == 0) {
		return 0;
	}

	Set<Integer> set = Arrays.stream(nums).boxed()
						.collect(Collectors.toSet());
	int max = 1;
	
	for(int num : nums) {
		int left = num - 1;
		int right = num + 1;
		while(set.remove(left)) left--;
		while(set.remove(right)) right++;
		ans = Math.max(ans,right - left - 1);
		if(set.isEmpty()) return ans;//save time if there are items in nums, but no item in hashset.
	}
	return ans;
}

Using Array Indices as Hash

Another idea is to map the original array to a new array with a length equal to the largest element in the original array. Then, iterate through this new array to find the longest consecutive sequence. However, if the largest element is very large, this approach may become inefficient.

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(n)