#12 · Arrays & Hashing

Longest Consecutive Sequence

Given an unsorted array of integers, return the length of the longest run of consecutive values (like 1, 2, 3, 4), regardless of their order in the array. The solution must run in O(n) time.

MediumLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Hash set

Gives O(1) membership checks, which is exactly what "is x + 1 present?" needs. With it, you can walk a run without sorting, as long as you only start from the first element of each run.

Memory layout

A table of buckets holding the distinct values (duplicates vanish). Lookups are scattered memory accesses, but each is O(1) on average, which pays off against O(n) scans or O(n log n) sorting.

Operation	Cost
insert / contains	O(1) average
build from n numbers	O(n)
space	O(n)

Hash map of run lengths at endpoints

Instead of walking a run, store its length at its two ends. When a new number arrives, the lengths stored at x − 1 and x + 1 tell you how big the runs on each side are, so merging is O(1).

Memory layout

A hash map from integer to integer. Only the endpoints of each run hold an up-to-date length, which is all the algorithm ever reads.

Operation	Cost
process one number	O(1) average (2 reads, 3 writes)
total	O(n) time, O(n) space

Why it fits

The values are unsorted and sorting would cost O(n log n), but the question is only about neighbours (x and x + 1), which a hash set answers directly in O(1).
A run is counted exactly once if you only start counting at numbers whose predecessor (x − 1) is absent. Every other element sits inside a run that some start will walk, so total walking is O(n).
The endpoint-length map pushes this further: each number triggers a constant amount of work and no walking at all.

Why alternatives degrade

Sorting:: O(n log n), which violates the required O(n) bound, though it is a perfectly good practical solution.
Counting from every element:: Re-walks the same run from each of its members (the O(n²) trap): a run of length k is walked k times, k²/2 steps in all.
Bitmap / boolean array over the value range:: O(1) per lookup, but needs memory proportional to (max − min), which can be astronomically larger than n for sparse values such as 10⁹.

Four approaches, from naive to production

1 · beginner

Extend from every number with a linear search

time O(n³) worst casespace O(1)

For each number, keep asking "is start + 1 in the array? is start + 2?" by scanning the array until the run ends, and keep the best length.

int longestConsecutive(vector<int>& nums) {
    int best = 0;
    for (int start : nums) {
        int len = 1;
        while (find(nums.begin(), nums.end(), (long long)start + len) != nums.end()) len++;
        best = max(best, len);
    }
    return best;
}

public int longestConsecutive(int[] nums) {
    int best = 0;
    for (int start : nums) {
        int len = 1;
        while (has(nums, (long) start + len)) len++;
        best = Math.max(best, len);
    }
    return best;
}

private boolean has(int[] nums, long v) {
    for (int x : nums) if (x == v) return true;
    return false;
}

def longest_consecutive(nums: list[int]) -> int:
    best = 0
    for start in nums:
        length = 1
        while start + length in nums: length += 1
        best = max(best, length)
    return best

function longestConsecutive(nums: number[]): number {
  let best = 0;
  for (const start of nums) {
    let len = 1;
    while (nums.includes(start + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}

Flaws & bottlenecks

Each "is it present?" is an O(n) scan, and a run of length k is walked from each of its k members, so the cost is up to O(n³).
Counts the same run repeatedly: starting from 1, 2, 3 and 4 all rediscover (parts of) the run 1–4.
No use of the fact that membership could be made O(1).

Interviewer cross-questions

Where does the cubic cost come from?

Say: n choices of start × up to n steps of extension × an O(n) scan per step (includes). Replacing the scan with a set lookup removes one factor of n, and starting only at run beginnings removes another.

Do duplicates matter?

Say: They only waste work here (the same start is re-explored). In the set-based versions, duplicates disappear automatically, since a set keeps one copy.

How do you fix the repeated counting of the same run?

Say: Only begin counting at a number whose predecessor x − 1 is NOT in the array: that is the first element of a run. Every element belongs to exactly one run, so each run is walked once.

2 · intermediate

Sort and count runs

time O(n log n)space O(n)

Deduplicate and sort the numbers. Consecutive values become neighbours, so scan once, extending the run when the next value is previous + 1 and restarting otherwise.

int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) return 0;
    vector<int> sorted(nums); sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    int best = 1;
    int run = 1;
    for (size_t i = 1; i < sorted.size(); i++) {
        if ((long long)sorted[i] == (long long)sorted[i - 1] + 1) run++;
        else run = 1;
        best = max(best, run);
    }
    return best;
}

public int longestConsecutive(int[] nums) {
    if (nums.length == 0) return 0;
    int[] sorted = Arrays.stream(nums).distinct().sorted().toArray();
    int best = 1;
    int run = 1;
    for (int i = 1; i < sorted.length; i++) {
        if ((long) sorted[i] == (long) sorted[i - 1] + 1) run++;
        else run = 1;
        best = Math.max(best, run);
    }
    return best;
}

def longest_consecutive(nums: list[int]) -> int:
    if not nums: return 0
    ordered = sorted(set(nums))
    best = 1
    run = 1
    for i in range(1, len(ordered)):
        if ordered[i] == ordered[i - 1] + 1: run += 1
        else: run = 1
        best = max(best, run)
    return best

function longestConsecutive(nums: number[]): number {
  if (nums.length === 0) return 0;
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  let best = 1;
  let run = 1;
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1] + 1) run++;
    else run = 1;
    best = Math.max(best, run);
  }
  return best;
}

Flaws & bottlenecks

O(n log n) from sorting, which misses the O(n) the problem requires.
Needs a deduplicated copy: an O(n) extra array (or an in-place sort that mutates the input).
Sorting orders the whole array although only neighbour relationships matter.

Interviewer cross-questions

Why remove duplicates before the scan?

Say: Equal neighbours are neither "previous + 1" nor a gap, so they would reset the run incorrectly (or you must special-case them). Deduplicating first keeps the loop simple.

Is this a valid answer in an interview?

Say: Yes, as a stepping stone: it is simple, obviously correct, and often fast in practice. The follow-up is "can you do it in O(n)?", which leads to the hash-set solution.

Could a radix sort make it linear?

Say: For fixed-width integers a radix sort is O(n · w) (w = number of digit passes), which is linear in n. It does work for 32-bit values, but it needs extra buffers and is more code than a hash set.

3 · advanced

Hash set, start only at run beginnings

time O(n)space O(n)

Load all numbers into a set. For each x, skip it if x − 1 exists; otherwise x starts a run, so count upward while end + 1 is in the set.

int longestConsecutive(vector<int>& nums) {
    unordered_set<long long> set(nums.begin(), nums.end());
    int best = 0;
    for (long long x : set) {
        if (set.count(x - 1)) continue;
        long long end = x;
        while (set.count(end + 1)) end++;
        best = max(best, (int)(end - x + 1));
    }
    return best;
}

public int longestConsecutive(int[] nums) {
    Set<Long> set = new HashSet<>();
    for (int v : nums) set.add((long) v);
    int best = 0;
    for (long x : set) {
        if (set.contains(x - 1)) continue;
        long end = x;
        while (set.contains(end + 1)) end++;
        best = Math.max(best, (int) (end - x + 1));
    }
    return best;
}

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

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

Flaws & bottlenecks

Each element may be touched twice (in the outer loop, and inside the walk from its run's start), so the constant is higher than the single-pass version.
Hash costs (hashing, memory scatter, resizing), with poor cache locality compared with a sorted scan.
Subtle: dropping the "x − 1 is absent" check silently turns O(n) into O(n²) while still giving correct answers, so a performance test is needed.

Interviewer cross-questions

Why is this O(n) even though there is a while loop inside the for loop?

Say: The while loop only runs from run STARTS, and each run is walked exactly once, from its first element to its last. Summed over all starts, the walking touches each element at most once, plus O(1) work per element in the outer loop, giving about 2n total.

What if you remove the x − 1 check?

Say: The answer is still correct but the complexity degrades to O(n²) in the worst case: for a run of length k, every element would walk the rest of the run, k + (k−1) + ... = k²/2 steps. The check is what prevents re-walking.

How do you handle huge n?

Say: Shard the values by range (or hash) across machines, compute local runs, and merge runs at shard boundaries. A set per shard keeps memory bounded, and only boundary values need to be exchanged.

4 · expert

Single pass, lengths stored at run endpoints

time O(n)space O(n)

Keep a map where each run's length is stored at its two endpoints. When a number arrives, read the runs on each side (x − 1 and x + 1), compute the merged length, and write it to the new endpoints.

int longestConsecutive(const vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return n;
    unordered_map<long long, int> span;
    span.reserve(2 * n);
    int best = 1;
    for (int i = 0; i < n; i++) {
        long long x = nums[i];
        if (span.count(x)) continue;
        int left = span.count(x - 1) ? span[x - 1] : 0;
        int right = span.count(x + 1) ? span[x + 1] : 0;
        int len = left + right + 1;
        span[x] = len;
        span[x - left] = len;
        span[x + right] = len;
        if (len > best) best = len;
    }
    return best;
}

public int longestConsecutive(int[] nums) {
    int n = nums.length;
    if (n < 2) return n;
    Map<Long, Integer> span = new HashMap<>(2 * n);
    int best = 1;
    for (int i = 0; i < n; i++) {
        long x = nums[i];
        if (span.containsKey(x)) continue;
        int left = span.getOrDefault(x - 1, 0);
        int right = span.getOrDefault(x + 1, 0);
        int len = left + right + 1;
        span.put(x, len);
        span.put(x - left, len);
        span.put(x + right, len);
        if (len > best) best = len;
    }
    return best;
}

def longest_consecutive(nums: Sequence[int]) -> int:
    n = len(nums)
    if n < 2: return n
    span: dict[int, int] = {}
    best = 1
    for i in range(n):
        x = nums[i]
        if x in span: continue
        left = span.get(x - 1, 0)
        right = span.get(x + 1, 0)
        length = left + right + 1
        span[x] = length
        span[x - left] = length
        span[x + right] = length
        if length > best: best = length
    return best

function longestConsecutive(nums: ArrayLike<number>): number {
  const n = nums.length;
  if (n < 2) return n;
  const span = new Map<number, number>();
  let best = 1;
  for (let i = 0; i < n; i++) {
    const x = nums[i];
    if (span.has(x)) continue;
    const left = span.get(x - 1) ?? 0;
    const right = span.get(x + 1) ?? 0;
    const len = left + right + 1;
    span.set(x, len);
    span.set(x - left, len);
    span.set(x + right, len);
    if (len > best) best = len;
  }
  return best;
}

Flaws & bottlenecks

Interior values keep stale lengths, so correctness relies on the invariant that only endpoints are ever read, which is subtle to maintain and to explain.
Three map writes per new number: more hashing work than the read-only set approach for easy inputs.
Does not recover which numbers form the run; it returns only the length.

Interviewer cross-questions

Why are stale interior lengths harmless?

Say: A new number x only ever reads x − 1 and x + 1. If x − 1 were an interior value of an existing run, then x would already be inside that run (and so already present and skipped). So the only values read are run endpoints, and endpoints are always kept current.

How is this like union-find?

Say: It is a degenerate union-find on a line: each run is a set, merging adjacent runs is a union, and storing the size at both endpoints stands in for the representative and size lookup. No path compression is needed because only O(1) neighbours are consulted.

What are the edge cases?

Say: Duplicates (skipped via the has check), x − 1 or x + 1 overflowing at the integer limits (use a wider type), negative numbers, n < 2, and all-equal arrays (answer 1).

Synchronized code walkthrough

Showing: Extend from every number with a linear search — shares the player above; click any step to jump.

int longestConsecutive(vector<int>& nums) {
    int best = 0;
    for (int start : nums) {
        int len = 1;
        while (find(nums.begin(), nums.end(), (long long)start + len) != nums.end()) len++;
        best = max(best, len);
    }
    return best;
}

public int longestConsecutive(int[] nums) {
    int best = 0;
    for (int start : nums) {
        int len = 1;
        while (has(nums, (long) start + len)) len++;
        best = Math.max(best, len);
    }
    return best;
}

private boolean has(int[] nums, long v) {
    for (int x : nums) if (x == v) return true;
    return false;
}

def longest_consecutive(nums: list[int]) -> int:
    best = 0
    for start in nums:
        length = 1
        while start + length in nums: length += 1
        best = max(best, length)
    return best

function longestConsecutive(nums: number[]): number {
  let best = 0;
  for (const start of nums) {
    let len = 1;
    while (nums.includes(start + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}

int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) return 0;
    vector<int> sorted(nums); sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    int best = 1;
    int run = 1;
    for (size_t i = 1; i < sorted.size(); i++) {
        if ((long long)sorted[i] == (long long)sorted[i - 1] + 1) run++;
        else run = 1;
        best = max(best, run);
    }
    return best;
}

public int longestConsecutive(int[] nums) {
    if (nums.length == 0) return 0;
    int[] sorted = Arrays.stream(nums).distinct().sorted().toArray();
    int best = 1;
    int run = 1;
    for (int i = 1; i < sorted.length; i++) {
        if ((long) sorted[i] == (long) sorted[i - 1] + 1) run++;
        else run = 1;
        best = Math.max(best, run);
    }
    return best;
}

def longest_consecutive(nums: list[int]) -> int:
    if not nums: return 0
    ordered = sorted(set(nums))
    best = 1
    run = 1
    for i in range(1, len(ordered)):
        if ordered[i] == ordered[i - 1] + 1: run += 1
        else: run = 1
        best = max(best, run)
    return best

function longestConsecutive(nums: number[]): number {
  if (nums.length === 0) return 0;
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  let best = 1;
  let run = 1;
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1] + 1) run++;
    else run = 1;
    best = Math.max(best, run);
  }
  return best;
}

int longestConsecutive(vector<int>& nums) {
    unordered_set<long long> set(nums.begin(), nums.end());
    int best = 0;
    for (long long x : set) {
        if (set.count(x - 1)) continue;
        long long end = x;
        while (set.count(end + 1)) end++;
        best = max(best, (int)(end - x + 1));
    }
    return best;
}

public int longestConsecutive(int[] nums) {
    Set<Long> set = new HashSet<>();
    for (int v : nums) set.add((long) v);
    int best = 0;
    for (long x : set) {
        if (set.contains(x - 1)) continue;
        long end = x;
        while (set.contains(end + 1)) end++;
        best = Math.max(best, (int) (end - x + 1));
    }
    return best;
}

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

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

int longestConsecutive(const vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return n;
    unordered_map<long long, int> span;
    span.reserve(2 * n);
    int best = 1;
    for (int i = 0; i < n; i++) {
        long long x = nums[i];
        if (span.count(x)) continue;
        int left = span.count(x - 1) ? span[x - 1] : 0;
        int right = span.count(x + 1) ? span[x + 1] : 0;
        int len = left + right + 1;
        span[x] = len;
        span[x - left] = len;
        span[x + right] = len;
        if (len > best) best = len;
    }
    return best;
}

public int longestConsecutive(int[] nums) {
    int n = nums.length;
    if (n < 2) return n;
    Map<Long, Integer> span = new HashMap<>(2 * n);
    int best = 1;
    for (int i = 0; i < n; i++) {
        long x = nums[i];
        if (span.containsKey(x)) continue;
        int left = span.getOrDefault(x - 1, 0);
        int right = span.getOrDefault(x + 1, 0);
        int len = left + right + 1;
        span.put(x, len);
        span.put(x - left, len);
        span.put(x + right, len);
        if (len > best) best = len;
    }
    return best;
}

def longest_consecutive(nums: Sequence[int]) -> int:
    n = len(nums)
    if n < 2: return n
    span: dict[int, int] = {}
    best = 1
    for i in range(n):
        x = nums[i]
        if x in span: continue
        left = span.get(x - 1, 0)
        right = span.get(x + 1, 0)
        length = left + right + 1
        span[x] = length
        span[x - left] = length
        span[x + right] = length
        if length > best: best = length
    return best

function longestConsecutive(nums: ArrayLike<number>): number {
  const n = nums.length;
  if (n < 2) return n;
  const span = new Map<number, number>();
  let best = 1;
  for (let i = 0; i < n; i++) {
    const x = nums[i];
    if (span.has(x)) continue;
    const left = span.get(x - 1) ?? 0;
    const right = span.get(x + 1) ?? 0;
    const len = left + right + 1;
    span.set(x, len);
    span.set(x - left, len);
    span.set(x + right, len);
    if (len > best) best = len;
  }
  return best;
}