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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Longest Consecutive Sequence and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →