Problem Statement

Given an unsorted array of integers, find the length of the longest consecutive sequence of numbers in it. A consecutive sequence means the numbers in the sequence are contiguous without any gaps. For instance, 1, 2, 3, 4 is a consecutive sequence, but 1, 3, 4, 5 is not.

Examples

1. • Input: [10, 11, 14, 12, 13]
   • Output: 5
   • Justification: The entire array forms a consecutive sequence from 10 to 14.
2. • Input: [3, 6, 4, 100, 101, 102]
   • Output: 3
   • Justification: There are two consecutive sequences, [3, 4] and [100,101,102]. The latter has a maximum length of 3.
3. • Input: [4, 3, 6, 2, 5, 8, 4, 7, 0, 1]
   • Output: 9
   • Justification: The longest consecutive sequences here are [0, 1, 2, 3, 4, 5, 6, 7, 8].
4. • Input: [7, 8, 10, 11, 15]
   • Output: 2
   • Justification: The longest consecutive sequences here are [7,8] and [10,11], both of length 2.

Constraints:

• 0 <= nums.length <= 10⁵
• -10⁹ <= nums[i] <= 10⁹

Solution

To solve this problem, the key observation is that if n is part of a consecutive sequence, then n+1 and n-1 must also be in that sequence.

1. HashSet: Begin by inserting all elements of the array into a HashSet. The reason for using a HashSet is to ensure O(1) time complexity during look-up operations.

2. Initial Scan: Iterate through each element of the array. For every number, check if it's the starting point of a possible sequence. This can be determined by checking if n-1 exists in the HashSet. If not, then it means n is the start of a sequence.

3. Building Sequences: For each starting number identified in step 2, keep checking if n+1, n+2... exist in the HashSet. For each present number, increase the length of the sequence and move to the next number.

4. Result: Store the length of each sequence found in step 3. The answer will be the longest of all sequences identified.

Algorithm Walkthrough

Let's trace the second example, [3, 6, 4, 100, 101, 102]. Move through the steps one at a time:

Code