Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. This problem is a classic interview question that tests your ability to efficiently identify and track sequences within a dataset. It's useful in scenarios like analyzing user activity patterns or identifying contiguous data ranges.

Problem Description

You are given an array of integers, which may contain duplicates and is not necessarily sorted. Your task is to determine the length of the longest consecutive sequence that exists within the array. A consecutive sequence is defined as a set of numbers where each number is exactly one greater than the previous number.

What needs to be achieved:

• Identify all consecutive sequences within the input array.
• Determine the length of the longest sequence found.
• Return the length of the longest consecutive sequence.

Key Requirements:

• The input array can contain positive, negative, and zero values.
• The input array may contain duplicate values.
• The order of elements in the input array is not guaranteed.
• The output should be a single integer representing the length of the longest consecutive sequence.

Expected Behavior:

The function should return the length of the longest consecutive sequence. If the input array is empty, it should return 0. If there are no consecutive sequences, it should return 0.

Edge Cases to Consider:

• Empty input array.
• Array with only one element.
• Array with all duplicate elements.
• Array with a mix of positive, negative, and zero values.
• Long arrays with many potential consecutive sequences.

Examples

Example 1:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive sequence is [1, 2, 3, 4]. Its length is 4.

Example 2:

Input: [0,3,7,2,5,8,4,6,0,1]
Output: 9
Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8]. Its length is 9.

Example 3:

Input: []
Output: 0
Explanation: The input array is empty, so there are no consecutive sequences.

Example 4:

Input: [1,2,0,1]
Output: 3
Explanation: The longest consecutive sequence is [0, 1, 2]. Its length is 3. Note that duplicates are handled correctly.

Constraints

• The input array can contain up to 20,000 elements.
• The values in the input array can range from -1,000,000 to 1,000,000.
• The solution should have a time complexity of O(n), where n is the number of elements in the input array. A naive O(n^2) solution will likely fail due to the constraints.
• The solution should have a space complexity of O(n) in the worst case.

Notes

Consider using a set (or hash table) to efficiently check for the existence of elements in the array. This will be crucial for achieving the desired time complexity. Think about how to avoid redundant checks and ensure that each element is processed only once. The key is to avoid sorting the array, as that would increase the time complexity. Focus on identifying the start of each consecutive sequence and then extending it as far as possible.