Longest Consecutive Subsequence: O(n) Algorithm Optimization

Problem Statement

Given an unsorted array of integers, the task is to return the length of the longest consecutive elements sequence while ensuring an algorithm with O(n) time complexity. The goal is to calculate the longest chain of consecutive numbers present in the array.

Key constraints include:

• 0 ≤ nums.length ≤ 10^5
• -10^9 ≤ nums[i] ≤ 10^9

This guide explains various approaches to solving the problem, including naive, sorting, and optimal HashSet-based methods.

Detailed Examples and Explanations

Example 1

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4

Explanation: The longest consecutive sequence is [1, 2, 3, 4].
Natural question: How do you determine the start of a sequence?
By checking if the preceding number (num – 1) does not exist in the array, we can confirm the beginning of a consecutive chain.

Example 2

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

Explanation: Although duplicates exist, they are ignored. The consecutive sequence is effectively [0, 1, 2, 3, 4, 5, 6, 7, 8].

Example 3

Input: nums = [1, 0, 1, 2]
Output: 3

Explanation: The consecutive sequence is [0, 1, 2]. Duplicate entries are not counted more than once.

Approaches and Algorithm Optimization

Naive Approach

The intuitive method involves iterating through each element and checking if the next consecutive element exists in the array. Although straightforward, it has a worst-case time complexity of O(n²) due to repeated searches.

Step-by-Step Process:

• Iterate over each element.
• For each element, check if the next consecutive number exists.
• Count consecutive numbers and update the maximum length.

Issue : Inefficient for large inputs due to repeated searching.