128. Longest Consecutive Sequence (Medium)

Problem

Given an unsorted array of integers nums, return the length of the longest consecutive-integer sequence. The algorithm must run in $O(n)$ time.

Example

nums = [100, 4, 200, 1, 3, 2] → 4 (the sequence [1, 2, 3, 4])
nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] → 9

LeetCode 128 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, for each number, walk forward

For each number x, linearly scan the array for x+1, x+2, until a miss.

def longest_consecutive(nums: list[int]) -> int:
    best = 0                              # L1: O(1)
    for x in nums:                        # L2: outer loop, n iterations
        cur = x                           # L3: O(1)
        length = 1                        # L4: O(1)
        while cur + 1 in nums:            # L5: O(n) membership on a list, per call
            cur += 1                      # L6: O(1)
            length += 1                   # L7: O(1)
        best = max(best, length)          # L8: O(1)
    return best

function longestConsecutive(nums: number[]): number {
    let best = 0;                                      // L1: O(1)
    for (const x of nums) {                            // L2: outer loop, n iterations
        let cur = x;                                   // L3: O(1)
        let length = 1;                                // L4: O(1)
        while (nums.includes(cur + 1)) {              // L5: O(n) membership per call
            cur++;                                     // L6: O(1)
            length++;                                  // L7: O(1)
        }
        best = Math.max(best, length);                 // L8: O(1)
    }
    return best;
}

func longestConsecutive(nums []int) int {
  best := 0                                          // L1: O(1)
  for _, x := range nums {                           // L2: outer loop, n iterations
    cur := x                                       // L3: O(1)
    length := 1                                    // L4: O(1)
    for contains(nums, cur+1) {                    // L5: O(n) membership per call
      cur++                                      // L6: O(1)
      length++                                   // L7: O(1)
    }
    if length > best { best = length }             // L8: O(1)
  }
  return best
}

func contains(nums []int, v int) bool {
  for _, n := range nums {
    if n == v { return true }
  }
  return false
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2 (outer loop)	$O(1)$	n	$O(n)$
L5 (list membership)	$O(n)$	up to n per outer iteration	$O(n³)$ ← dominates
L3, L4, L6, L7, L8	$O(1)$	proportional to run lengths	$O(n²)$ at most

Each in nums on a list costs $O(n)$ , called up to n times per outer loop iteration.

Complexity

Time: $O(n³)$ in the worst case, driven by L5 ( $O(n)$ membership called up to n times per outer).
Space: $O(1)$ extra.

Clearly doesn’t meet the $O(n)$ requirement, useful to see what the naive instinct would cost.

Swift

final class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        let values = Set(nums); var best = 0
        for value in nums { var current = value, length = 0; while values.contains(current) { length += 1; current += 1 }; best = max(best, length) }
        return best
    }
}

Approach 2: Sort, then count runs

After sorting, runs of consecutive integers are adjacent. Walk the sorted array.

def longest_consecutive(nums: list[int]) -> int:
    if not nums:                                    # L1: O(1) guard
        return 0
    nums_sorted = sorted(set(nums))                 # L2: O(n log n) sort after O(n) dedup
    best = cur = 1                                  # L3: O(1)
    for i in range(1, len(nums_sorted)):            # L4: loop, n iterations
        if nums_sorted[i] == nums_sorted[i - 1] + 1:  # L5: O(1) comparison
            cur += 1                                # L6: O(1)
            best = max(best, cur)                   # L7: O(1)
        else:
            cur = 1                                 # L8: O(1) reset
    return best

function longestConsecutive(nums: number[]): number {
    if (!nums.length) return 0;                     // L1: O(1) guard
    const sorted = [...new Set(nums)].sort((a, b) => a - b); // L2: O(n log n)
    let best = 1, cur = 1;                          // L3: O(1)
    for (let i = 1; i < sorted.length; i++) {       // L4: loop, n iterations
        if (sorted[i] === sorted[i - 1] + 1) {      // L5: O(1) comparison
            cur++;                                   // L6: O(1)
            best = Math.max(best, cur);             // L7: O(1)
        } else {
            cur = 1;                                 // L8: O(1) reset
        }
    }
    return best;
}

func longestConsecutive(nums []int) int {
  if len(nums) == 0 { return 0 }              // L1: O(1) guard
  seen := make(map[int]struct{})
  for _, n := range nums { seen[n] = struct{}{} }
  unique := make([]int, 0, len(seen))
  for n := range seen { unique = append(unique, n) }
  sort.Ints(unique)                            // L2: O(n log n) sort after dedup
  best, cur := 1, 1                            // L3: O(1)
  for i := 1; i < len(unique); i++ {          // L4: loop, n iterations
    if unique[i] == unique[i-1]+1 {          // L5: O(1) comparison
      cur++                                // L6: O(1)
      if cur > best { best = cur }         // L7: O(1)
    } else {
      cur = 1                              // L8: O(1) reset
    }
  }
  return best
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L2 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates
L4-L8 (linear scan)	$O(1)$	n	$O(n)$

The sort owns the cost; the rest is a single linear pass.

Complexity

Time: $O(n log n)$ , dominated by L2 (the sort).
Space: $O(n)$ for the sorted set.

Correct and simple, but violates the explicit $O(n)$ constraint in the prompt.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        guard !nums.isEmpty else { return 0 }
        let sorted = nums.sorted(); var best = 1, current = 1
        for index in 1..<sorted.count { if sorted[index] == sorted[index - 1] { continue }; if sorted[index] == sorted[index - 1] + 1 { current += 1 } else { current = 1 }; best = max(best, current) }
        return best
    }
}

Approach 3: Hash set + run-start detection (optimal)

Put everything in a set. For each number, only start counting a run if x - 1 is not in the set (so x is a run start). Then walk upward as long as the next integer is present.

Each element is touched by a walking pointer at most once across the whole algorithm, giving total $O(n)$ .

def longest_consecutive(nums: list[int]) -> int:
    num_set = set(nums)                    # L1: O(n) set construction
    best = 0                               # L2: O(1)
    for x in num_set:                      # L3: outer loop, n iterations
        if x - 1 in num_set:              # L4: O(1) set lookup, skip non-starts
            continue
        cur = x                            # L5: O(1)
        length = 1                         # L6: O(1)
        while cur + 1 in num_set:         # L7: O(1) set lookup per call
            cur += 1                       # L8: O(1)
            length += 1                    # L9: O(1)
        best = max(best, length)           # L10: O(1)
    return best

function longestConsecutive(nums: number[]): number {
    const numSet = new Set(nums);                   // L1: O(n) set construction
    let best = 0;                                   // L2: O(1)
    for (const x of numSet) {                       // L3: outer loop, n iterations
        if (numSet.has(x - 1)) continue;            // L4: O(1) set lookup, skip non-starts
        let cur = x;                                // L5: O(1)
        let length = 1;                             // L6: O(1)
        while (numSet.has(cur + 1)) {              // L7: O(1) set lookup per call
            cur++;                                  // L8: O(1)
            length++;                               // L9: O(1)
        }
        best = Math.max(best, length);              // L10: O(1)
    }
    return best;
}

func longestConsecutive(nums []int) int {
  numSet := make(map[int]struct{})
  for _, n := range nums { numSet[n] = struct{}{} } // L1: O(n) set construction
  best := 0                                          // L2: O(1)
  for x := range numSet {                            // L3: outer loop, n iterations
    if _, ok := numSet[x-1]; ok { continue }      // L4: O(1) set lookup, skip non-starts
    cur := x                                       // L5: O(1)
    length := 1                                    // L6: O(1)
    for {
      if _, ok := numSet[cur+1]; !ok { break }  // L7: O(1) set lookup per call
      cur++                                      // L8: O(1)
      length++                                   // L9: O(1)
    }
    if length > best { best = length }             // L10: O(1)
  }
  return best
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (set construction)	$O(n)$	1	$O(n)$
L3 (outer loop)	$O(1)$	n	$O(n)$
L4 (skip non-starts)	$O(1)$	n	$O(n)$
L7 (inner while, set lookup)	$O(1)$	n total across all starts	$O(n)$ ← key insight
L10 (max)	$O(1)$	per start	$O(n)$

L4’s guard ensures each element is walked from its run-start exactly once. Even though L7 is inside a while loop, the total number of iterations across all outer iterations is at most n (each element visited once as a “next” step).

Complexity

Time: $O(n)$ , driven by L1 (set build) plus the amortized- $O(n)$ total inner-while work at L7.
Space: $O(n)$ for the set.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Alternative: Union-Find

A second $O(n)$ approach unions every x with x - 1 and x + 1 in a disjoint-set structure and returns the largest component size. Same asymptotics, more code, worth knowing for the pattern.

Swift

final class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        let values = Set(nums); var best = 0
        for value in values where !values.contains(value - 1) { var current = value, length = 1; while values.contains(current + 1) { current += 1; length += 1 }; best = max(best, length) }
        return best
    }
}

Summary

Approach	Time	Space
For-each + linear search	$O(n³)$	$O(1)$
Sort + count	$O(n log n)$	$O(n)$
Hash set + run start	$O(n)$	$O(n)$

The run-start trick is exact-fit to the problem’s constraint. Recognize “I need $O(n)$ but I also need order” as the signal to reach for a hash set with an invariant.

# Quick smoke tests, paste into a REPL or save as test_longest_consecutive.py and run.
# Uses the canonical implementation (Approach 3: hash set + run-start detection).

def longest_consecutive(nums: list[int]) -> int:
    num_set = set(nums)
    best = 0
    for x in num_set:
        if x - 1 in num_set:
            continue
        cur = x
        length = 1
        while cur + 1 in num_set:
            cur += 1
            length += 1
        best = max(best, length)
    return best

def _run_tests():
    assert longest_consecutive([100, 4, 200, 1, 3, 2]) == 4
    assert longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) == 9
    assert longest_consecutive([]) == 0
    assert longest_consecutive([1]) == 1
    assert longest_consecutive([1, 2, 3, 4, 5]) == 5
    assert longest_consecutive([5, 4, 3, 2, 1]) == 5
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function longestConsecutive(nums: number[]): number {
    const numSet = new Set(nums);
    let best = 0;
    for (const x of numSet) {
        if (numSet.has(x - 1)) continue;
        let cur = x;
        let length = 1;
        while (numSet.has(cur + 1)) { cur++; length++; }
        best = Math.max(best, length);
    }
    return best;
}

console.assert(longestConsecutive([100, 4, 200, 1, 3, 2]) === 4);
console.assert(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) === 9);
console.assert(longestConsecutive([]) === 0);
console.assert(longestConsecutive([1]) === 1);
console.assert(longestConsecutive([1, 2, 3, 4, 5]) === 5);
console.assert(longestConsecutive([5, 4, 3, 2, 1]) === 5);
console.log("all tests pass");

Arrays, input
Hash Tables, set membership for $O(1)$ lookups; run-start detection

Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.
Array Scans, the linear pass habit of carrying just enough state while reading each item once.

128. Longest Consecutive Sequence (Medium)

Problem

Try it yourself

Approach 1: Brute force, for each number, walk forward

Approach 2: Sort, then count runs

Approach 3: Hash set + run-start detection (optimal)

Alternative: Union-Find

Summary

Test cases

Related data structures

Related concepts