Problem

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

Examples

Example 1:

1
2
3

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:

1
2

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

Similar problem

Binary Tree Longest Consecutive Sequence

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
}

Complexity

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