Skip to main content

128. Longest Consecutive Sequence

medium

Find the length of the longest run of consecutive integers in an unsorted array — in O(n) time. The catch: avoid the obvious sort and use a hash set to detect run starts only.

By Sam K., Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

Example 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.

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sorting is O(n log n) — disallowed by the constraint. So you need a hash structure.

Hint 2

Stuff nums into a set. The trick: only start counting from a num whose num - 1 is NOT in the set — that's a run start.

Hint 3

From each run start, walk num + 1, num + 2, ... while they're in the set. Total work is still O(n) because each number is visited at most twice.

Solution approach

Reveal approach

Stuff every number into a hash set (auto-dedupes). Iterate the set. For each num, check if num - 1 is NOT in the set — if num - 1 is present, num is in the middle of a run and starting here would just re-walk. Only run-starts (num - 1 missing) get to expand: walk num + 1, num + 2, ... while in the set, tracking the run length. Track the max across all run-starts. Return it. The 'only start from a run start' trick is what keeps the algorithm linear — each number is visited at most twice (once during the run-start check, once during the expansion). Edge case: empty input returns 0.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • hash-set
  • union-find

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

More Hash Tables practice problems

See all Hash Tables problems →