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

Similar problem

Binary Tree Longest Consecutive Sequence Problem

Solution

Method 1 - Sorting

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).

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:

  1. 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.
  2. 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)