Longest Consecutive Element Sequence

Understanding patterns and sequences within data is a fundamental task in various computing domains. From analyzing time-series data to optimizing database queries or validating ranges, identifying consecutive elements can provide valuable insights. This challenge asks you to find the length of the longest sequence of consecutive integers within an unsorted collection.

Problem Description

You are given an unsorted array of integers. Your task is to find the length of the longest sequence of consecutive elements. A "consecutive sequence" is defined as a series of numbers where each number is exactly one greater than the preceding number, like [1, 2, 3, 4]. The numbers in the sequence do not need to appear contiguously in the input array. If the input array contains duplicate numbers, these duplicates should be considered only once when forming consecutive sequences.

Key requirements:

The input will be an array of integers.
The output should be a single integer representing the length of the longest consecutive sequence found.
An empty input array should result in a sequence length of 0.
An array with no consecutive elements (e.g., [1, 5, 9]) should result in a sequence length of 1 (each number forms a sequence of length 1 by itself).

Examples

Example 1:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The numbers 1, 2, 3, and 4 form a consecutive sequence. This is the longest such sequence found in the input array.

Example 2:

Input: [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Explanation: The distinct numbers from the input form the sequence [0, 1, 2, 3, 4, 5, 6, 7, 8]. This sequence has a length of 9. Note that the duplicate '0' does not affect the sequence length, as each distinct number is counted only once.

Example 3:

Input: []
Output: 0
Explanation: An empty array contains no elements, thus no consecutive sequence can be formed.

Example 4:

Input: [7, 7, 7, 7]
Output: 1
Explanation: The only distinct number present is 7. This forms a consecutive sequence of [7], which has a length of 1.

Constraints

The number of elements in the input array (N) will be between 0 and 10^5 (inclusive).
Each integer num in the array will be between -10^9 and 10^9 (inclusive).
Your solution must run in O(N) time complexity.
Your solution should aim for O(N) space complexity.

Notes

Consider how to efficiently check for the existence of num+1, num+2, etc., without repeatedly searching through the entire array.
The O(N) time complexity constraint suggests avoiding sorting the array if the sorting algorithm used is O(N log N). Think about data structures that offer average O(1) lookup times.
Pay attention to how you handle duplicate numbers in the input array; they should only contribute once to sequence formation.
Think about how to identify the "start" of a potential consecutive sequence to avoid redundant checks. For example, if you encounter the number 3, and 2 is also present in the input, it's generally more efficient to begin sequence checking from 2 (the actual start of the [2, 3] sequence) rather than from 3.

Longest Consecutive Element Sequence

Problem Description

Key requirements:

The input will be an array of integers.

The output should be a single integer representing the length of the longest consecutive sequence found.

An empty input array should result in a sequence length of 0.

An array with no consecutive elements (e.g., [1, 5, 9]) should result in a sequence length of 1 (each number forms a sequence of length 1 by itself).

Examples

Example 1:

Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The numbers 1, 2, 3, and 4 form a consecutive sequence. This is the longest such sequence found in the input array.

Example 2:

Input: [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] Output: 9 Explanation: The distinct numbers from the input form the sequence [0, 1, 2, 3, 4, 5, 6, 7, 8]. This sequence has a length of 9. Note that the duplicate '0' does not affect the sequence length, as each distinct number is counted only once.

Example 3:

Input: [] Output: 0 Explanation: An empty array contains no elements, thus no consecutive sequence can be formed.

Example 4:

Input: [7, 7, 7, 7] Output: 1 Explanation: The only distinct number present is 7. This forms a consecutive sequence of [7], which has a length of 1.

Notes

Consider how to efficiently check for the existence of num+1, num+2, etc., without repeatedly searching through the entire array.

The O(N) time complexity constraint suggests avoiding sorting the array if the sorting algorithm used is O(N log N). Think about data structures that offer average O(1) lookup times.

Pay attention to how you handle duplicate numbers in the input array; they should only contribute once to sequence formation.

Think about how to identify the "start" of a potential consecutive sequence to avoid redundant checks. For example, if you encounter the number 3, and 2 is also present in the input, it's generally more efficient to begin sequence checking from 2 (the actual start of the [2, 3] sequence) rather than from 3.