Explorer
Data Structures & Algorithms

Find length of the longest sequence of consecutive integers in O(N) time.

Problem Statement

Given an unsorted array of integers `nums`, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in `O(n)` time.

Examples

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

Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

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

Output: 9

Explanation: The longest sequence of consecutive integers is length 9.

Complexity

Time Complexity: O(N)

Space Complexity: O(N)

Hints

šŸ’” Hint 1: Sorting takes O(N log N). To achieve O(N), insert all numbers into a HashSet. šŸ’” Hint 2: Only start counting a sequence from numbers that are the start of a streak: i.e., set does not contain num - 1. šŸ’” Hint 3: For each streak starter, check num + 1, num + 2... in the set. Each element is visited at most twice.

Editorial & Approach

Problem Overview & Intuition

By inserting all numbers into a hash set, we can check for consecutive neighbors in O(1). We only begin expanding a sequence if num - 1 does not exist in the set. This ensures every element is traversed at most twice, resulting in linear O(N) time.

Step-by-Step Approach

  1. Store all elements in set = new Set(nums).
  2. Iterate through each num in the set.
  3. If !set.has(num - 1), this num is the beginning of a sequence.
  4. Count consecutive elements currentNum + 1 while present in the set.
  5. Update longestStreak = Math.max(longestStreak, currentStreak).
  6. Return longestStreak.

Optimal Implementation (JavaScript)

function longestConsecutive(nums) {
  const set = new Set(nums);
  let longestStreak = 0;
  for (let num of set) {
    if (!set.has(num - 1)) {
      let currentNum = num;
      let currentStreak = 1;
      while (set.has(currentNum + 1)) {
        currentNum += 1;
        currentStreak += 1;
      }
      longestStreak = Math.max(longestStreak, currentStreak);
    }
  }
  return longestStreak;
}

Complexity Analysis

Time Complexity O(N) ā€” each number is looked up a constant number of times.
Space Complexity O(N) ā€” hash set of size up to N.

Edge Cases & Corner Traps Handled

  • Empty array: returns 0.
  • Array of duplicate elements: returns 1.
  • Disjoint numbers: returns 1.

Longest Consecutive Sequence in an Array

Medium
Given an unsorted array of integers `nums`, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in `O(n)` time.
Example Scenarios
1Example 1
Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation:

The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

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

The longest sequence of consecutive integers is length 9.

Editor
Loading Editor...
nums =
[100, 4, 200, 1, 3, 2]
Output:Click "Run" above to execute and verify your code here.
4