Practice/Amazon/Leetcode 128. Longest Consecutive Sequence

Leetcode 128. Longest Consecutive Sequence

CodingOptional

Problem

Given an array of integers (which may be unsorted and contain duplicates), determine the length of the longest sequence of consecutive integers that can be formed using elements from the array.

A consecutive sequence is a set of numbers where each number is exactly one more than the previous number (e.g., 5, 6, 7, 8).

You must solve this problem in O(n) time complexity, where n is the length of the input array.

Requirements

1. Return the length of the longest consecutive integer sequence
2. The elements in the original array don't need to be adjacent to form a sequence
3. Your solution must run in linear O(n) time
4. Handle edge cases including empty arrays and duplicate values

Constraints

• 0 ≤ nums.length ≤ 105
• -109 ≤ nums[i] ≤ 109
• Time complexity must be O(n)
• Space complexity should be O(n)

Examples

Example 1:

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

Example 2:

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] Output: 9 Explanation: The sequence [0, 1, 2, 3, 4, 5, 6, 7, 8] has length 9.

Example 3:

Input: nums = [9, 1, 4, 7, 3, 2, 8, 5, 6] Output: 9 Explanation: All numbers from 1 to 9 form a consecutive sequence.

Example 4:

Input: nums = [] Output: 0 Explanation: An empty array has no consecutive sequences.