Longest Consecutive Sequence - Problem

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.

A consecutive sequence is a sequence of integers where each number is exactly one more than the previous number.

Input & Output

Example 1 — Mixed Numbers
$ Input: nums = [100,4,200,1,3,2]
Output: 4
💡 Note: The longest consecutive elements sequence is [1,2,3,4], which has length 4
Example 2 — Duplicates
$ Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
💡 Note: The longest consecutive sequence is [0,1,2,3,4,5,6,7,8] with length 9
Example 3 — Single Element
$ Input: nums = [9]
Output: 1
💡 Note: Single element forms a sequence of length 1

Constraints

  • 0 ≤ nums.length ≤ 105
  • -109 ≤ nums[i] ≤ 109

Visualization

Tap to expand
Longest Consecutive Sequence: Find longest chain of consecutive numbersInput Array:1004200132Sequences:1234Length: 4100Length: 1200Length: 1Longest Sequence Length = 4Key insight: Use hash set to check for consecutive numbers in O(1) time
Understanding the Visualization
1
Input
Unsorted array [100,4,200,1,3,2]
2
Process
Find consecutive sequences: [1,2,3,4] and [100], [200]
3
Output
Length of longest sequence = 4
Key Takeaway
🎯 Key Insight: Only start counting sequences from numbers that have no predecessor (num-1 not in set)
Asked in
Google 45 Facebook 38 Amazon 32 Microsoft 28
78.0K Views
High Frequency
~25 min Avg. Time
1.9K Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen