Longest Consecutive Sequence

Difficulty: Medium

Problem

Given an unsorted integer array nums, find how long the longest streak of consecutive integers (each one exactly 1 more than the previous, e.g. 5, 6, 7) can be when using values from the array in any positions.

Example

Input: nums = [20, 6, 21, 3, 5, 4, 22, 7, 99]
Output: 5
Explanation: The values 3, 4, 5, 6, 7 are all present, forming a streak of length 5. The other streak, 20, 21, 22, has length 3.

Brute-force approach

Sort the array and find longest consecutive run.

Steps

  1. Sort the array
  2. Iterate and count consecutive elements
  3. Handle duplicates
  4. Track maximum streak

Time complexity: O(n log n) · Space complexity: O(1) or O(n)

Trade-offs

  • Sorting takes O(n log n)
  • Modifies array (or needs copy)
  • Can we avoid sorting?

Optimal approach

Key insight: A number is a sequence START only if (num - 1) is NOT present in the set!

Use a Set for O(1) lookup. Only start counting from sequence beginnings (no predecessor).

Steps

  1. Put all numbers into a HashSet
  2. Loop through numbers
  3. If (num-1) not in set → it's a sequence start
  4. Count consecutive numbers from that start
  5. Track the longest streak

Time complexity: O(n) · Space complexity: O(n)

Pseudocode

function longestConsecutive(nums):
    create set from nums
    longestStreak = 0
    
    for each num in set:
        if (num - 1) not in set:  // start of sequence
            currentNum = num
            currentStreak = 1
            
            while (currentNum + 1) in set:
                currentNum += 1
                currentStreak += 1
            
            longestStreak = max(longestStreak, currentStreak)
    
    return longestStreak

Hints

  • A set allows O(1) lookup
  • Only start counting from sequence beginnings (numbers with no predecessor)

Complexity questions

Time complexity of sorting approach?

O(n log n). Sorting is O(n log n), scanning is O(n)

Time complexity of the Set approach?

O(n). Each number is visited once for set creation, once during iteration

Why doesn't the while loop make it O(n²)?

Each element is counted in exactly one sequence. Each element is counted in exactly one sequence, so total work is O(n)

Space for the Set approach?

O(n). Store all n elements in the Set = O(n)

Check your understanding of Longest Consecutive Sequence

What is a consecutive sequence?

Numbers that follow each other (1,2,3). Consecutive means numbers that follow each other with no gaps.

Given [100, 4, 200, 1, 3, 2], what is the longest consecutive sequence?

[1, 2, 3, 4]. 1, 2, 3, 4 form a consecutive sequence of length 4.

Related problems

Keep practising