mafeshsho8lmafeshsho8l
Get Started
All coding questions

Longest Consecutive Sequence

medium
Blind 75NeetCode 150arrayshashing

Problem

Given an unsorted list of integers, find the length of the longest run of consecutive values. The values do not need to be adjacent in the list. Aim for linear time.

Examples

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
The run 1, 2, 3, 4 has length four.
Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
The run 0..8 has length nine.

Constraints

  • • 0 <= nums.length <= 10^5
  • • -10^9 <= nums[i] <= 10^9
Hints(tap to reveal)
  • 1. Put everything in a set for O(1) membership.
  • 2. Only start counting a run from a value that has no predecessor.
Optimal approach(spoiler)
  1. Insert all values into a hash set.
  2. For each value, check whether value minus one is absent; only then is it a run start.
  3. From a run start, walk upward while successive values exist, counting length.
  4. Track the maximum run length seen.
  5. Each value is visited at most twice, giving O(n) time.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor