Longest Consecutive Sequence

1. Problem & Core Objective

The problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

The sequence's elements must be consecutive integers, but they need not be adjacent in the array.

Input:  nums = [100, 4, 200, 1, 3, 2]         Output: 4      ([1,2,3,4])
Input:  nums = [0,3,7,2,5,8,4,6,0,1]          Output: 9      ([0..8])
Input:  nums = []                             Output: 0

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• You must write an algorithm that runs in O(n) time.

What the interviewer is actually testing

This is the hardest question in the section, and the one that most rewards careful reasoning.

1. The O(n) requirement is the entire problem. Sorting solves it trivially in O(n log n). The constraint explicitly forbids the easy path.
2. Can you find the pruning insight? The obvious hash-set solution looks O(n) but is secretly O(n²). Spotting why, and fixing it with a one-line guard, is the test.
3. Can you defend an amortized complexity argument? "This nested loop is actually O(n)" is the follow-up, every time.
4. Do you notice the value range blocks counting arrays? ±10^9 rules out indexing by value.

Most candidates reach a working solution. Far fewer can prove it's O(n). That proof is what's being marked.

2. First-Principles Thought Process

Step 1 — Read the constraints

n up to 10^5 — and the problem demands O(n).

That's unusual. Normally O(n log n) would be fine at this size, so the requirement is a deliberate instruction: the sorting solution exists, we know it, find something better.

Also note -10^9 <= nums[i] <= 10^9. The values are huge even though the count is small. So you cannot allocate an array indexed by value — that would need two billion slots. This rules out counting-sort style tricks and points at hashing.

Step 2 — The sorting solution (and why it's rejected)

Sort, then scan for the longest run of consecutive values, skipping duplicates.

O(n log n). Correct, simple — and explicitly disallowed. Present it as your baseline.

Step 3 — What does "consecutive" actually need?

To know whether n extends a sequence, you need to know whether n - 1 or n + 1 exist anywhere in the array. That's a membership question over the whole collection, not a positional one.

Membership in O(1) → HashSet.

So: dump everything into a set, and for each number walk upward while the next value exists.

Step 4 — The naive attempt, and its hidden cost

Set<Integer> set = new HashSet<>(...);
int best = 0;
for (int n : set) {
    int len = 1;
    while (set.contains(n + len)) len++;      // walk up from n
    best = Math.max(best, len);
}

Correct. But what's the complexity?

Take nums = [1, 2, 3, ..., 100000] — one long run.

• Starting at 1, the loop walks 100,000 steps.
• Starting at 2, it walks 99,999 steps.
• Starting at 3, 99,998…

Total ≈ n²/2. This is O(n²), not O(n) — it just doesn't look like it, because the nested loop is a while rather than a for.

Step 5 — The insight

Look at the waste: we walk the run 1,2,3,... starting from every one of its members. But every one of those walks is a suffix of the walk starting at 1. They tell us nothing new.

Only ever start walking from a number that BEGINS a run.

And how do you know n begins a run? Trivially:

n is a run-start if and only if n - 1 is not in the set.

If n - 1 exists, then n is in the middle of some run, and that run will be counted when we reach its true start. Skip it.

That's a one-line guard:

if (set.contains(n - 1)) continue;

Step 6 — Why this makes it O(n)

This is the argument to rehearse:

"The inner while only ever runs from the start of a run. A run of length L is walked exactly once — from its first element — costing L steps. The runs are disjoint, so their lengths sum to at most n. Total inner-loop work across the entire algorithm is therefore O(n), even though the code looks nested."

This is aggregate (amortized) accounting — bound the total work over the whole run, not the worst case of one iteration. The same reasoning justifies the monotonic stack (09) and the sliding window (08).

3. Solution Paths

Approach 1 — Brute force

public int longestConsecutive(int[] nums) {
    int best = 0;
    for (int n : nums) {
        int cur = n, len = 1;
        while (contains(nums, cur + 1)) { cur++; len++; }    // linear scan each time
        best = Math.max(best, len);
    }
    return best;
}

Where contains is a linear scan of the array.

• Time: O(n³) in the worst case — n starts × up to n steps × O(n) per lookup.
• Space: O(1).

Hopeless. Mention it only to motivate the set.

Counter-questions on this approach

⭐ "You said O(n³). Break that down."

Up to n starting points, each walking up to n steps, and each step doing an O(n) linear scan of the array to test membership. The membership test is the worst offender and the easiest to fix — moving to a HashSet immediately removes a whole factor of n.

Approach 2 — Sort, then scan

public int longestConsecutive(int[] nums) {
    if (nums.length == 0) return 0;

    Arrays.sort(nums);

    int best = 1, cur = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) continue;              // skip duplicates
        if (nums[i] == nums[i - 1] + 1) cur++;             // extends the run
        else cur = 1;                                      // run broken, restart
        best = Math.max(best, cur);
    }
    return best;
}

How it works. After sorting, consecutive integers become adjacent, so a single scan tracks run length.

The duplicate skip is essential. Without it, a repeat resets the run counter, because nums[i] == nums[i-1] is neither "equal" nor "one greater".

The counterexample is [1, 2, 2, 3]. Without the skip:

Returns 2; the correct answer is 3 (the run 1,2,3). Verified. The continue on duplicates fixes it.

Trace on [100, 4, 200, 1, 3, 2]:

Sorted: [1, 2, 3, 4, 100, 200]

Answer: 4 ✓

• Time: O(n log n).
• Space: O(1) extra (or O(log n) for the sort's stack), if mutating the input is allowed.

Rejected by the problem's O(n) requirement, but worth presenting: it's simple, it's correct, and it gives you a baseline to improve from. It's also the better real-world answer if memory is tight — it needs no hash set.

Counter-questions on this approach

⭐ "The problem requires O(n). Why show me an O(n log n) solution?"

As a baseline, and because it's genuinely the better choice in one scenario: it needs no hash set, so if memory were constrained this is what I'd ship. It's rejected here only because the problem states O(n) explicitly.

⭐ "What breaks if you drop the duplicate skip?"

[1,2,2,3] returns 2 instead of 3. The repeated 2 is neither equal to prev + 1 nor a continuation, so it resets the run counter mid-sequence. Verified — the skip isn't cosmetic.

"Conceptually, what's wrong with sorting here?"

It imposes a total ordering on all n elements when the question only needs local membership queries — does n+1 exist, does n−1 exist. Hashing answers exactly those and nothing more.

Approach 3 — Hash set without pruning (the trap)

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);

    int best = 0;
    for (int n : set) {
        int len = 1;
        while (set.contains(n + len)) len++;
        best = Math.max(best, len);
    }
    return best;
}

Correct but O(n²). On [1..100000] it walks 100,000 + 99,999 + … ≈ 5 × 10^9 steps.

Include it in your explanation as the step before the answer — showing you spotted the flaw yourself is worth more than skipping straight to the fix.

Counter-questions on this approach

⭐ "This uses a hash set and has one pass over it. Isn't it O(n)?"

No — it's O(n²), and that's exactly why it's worth showing. On [1, 2, …, n] the walk starts from 1 and takes n steps, then starts from 2 and takes n−1, then from 3, and so on: roughly n²/2 total. The while nested inside the for hides the cost because both use O(1) set operations, but the number of those operations is quadratic.

Approach 4 — Hash set with run-start pruning (optimal)

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);              // dedups automatically

    int best = 0;
    for (int n : set) {
        if (set.contains(n - 1)) continue;      // *** not a run start — skip ***

        int len = 1;
        while (set.contains(n + len)) len++;    // walk the run upward
        best = Math.max(best, len);
    }
    return best;
}

Trace on [100, 4, 200, 1, 3, 2]. Set: {1, 2, 3, 4, 100, 200}.

Answer: 4 ✓

Only three walks happened (from 1, 100, 200), and they covered every element exactly once. Three of the six iterations exited immediately on the guard.

• Time: O(n) — see the amortized argument in §2 step 6.
• Space: O(n) for the set.

Iterating set rather than nums is a small optimization: duplicates in nums would each trigger the guard check, which is harmless but wasteful. The set is already deduplicated.

Counter-questions on this approach

⭐ "Prove this is O(n). There's still a while inside a for."

The inner while only ever runs from the start of a run, because of the contains(n-1) guard. A run of length L is therefore walked exactly once, costing L steps. Runs are disjoint — no element belongs to two — so their lengths sum to at most n. Every non-start element exits on the guard in O(1). Total inner-loop work across the whole algorithm is bounded by n. That's aggregate accounting, the same argument that makes a monotonic stack linear.

⭐ "What breaks if you remove the continue?"

Correctness survives; complexity collapses to O(n²) — it becomes Approach 3 exactly. One line separates meeting the requirement from merely appearing to.

"HashSet is O(1) average. What's the worst case, and does it undermine your claim?"

Worst case is O(n) per operation under mass collisions, which would make the whole thing O(n²). Integer.hashCode is the identity function, so an adversary spacing values exactly by the table size could force collisions; Java treeifies large buckets to cap degradation at O(log n). The honest claim is "O(n) expected, assuming good hash distribution".

"Why iterate the set rather than the original array?"

The set is already deduplicated. Iterating nums would re-run the guard once per duplicate — harmless, but wasted work on inputs with many repeats.

Approach 5 — Union-Find (mention only)

Treat each value as a node, union n with n + 1 whenever both exist, then return the largest component size. O(n · α(n)) ≈ O(n).

Correct but over-engineered for this problem — more code, more memory, no complexity gain. Worth naming to show breadth; don't implement it unless asked. See 17 — Union-Find.

Counter-questions on this approach

⭐ "Union-Find is also near-linear. Why call it over-engineered?"

Because it buys nothing here. It's more code, more memory, and O(n · α(n)) rather than O(n) — all to solve a problem the set already handles in four lines. Where it genuinely earns its keep is the streaming variant, where elements arrive over time and runs must be merged incrementally. For a static array it's the wrong tool.

Comparison

4. Why the Optimal Wins

Against sorting. Sorting imposes a total ordering on all n elements. But the question only asks about local relationships — does n + 1 exist? You're computing a full ranking to answer a series of yes/no membership questions. Hashing answers exactly those questions and nothing more.

This is the same argument as Contains Duplicate, and it's the section's recurring theme:

If the question doesn't need order, hashing usually beats sorting.

Against the unpruned set version. Same data structure, same set operations — one continue separates O(n²) from O(n). The lesson is that a correct algorithm can still be the wrong algorithm, and you have to actually analyse the loop rather than assume while inside for is fine because both use a hash set.

The amortized argument is the deliverable. Rehearse it:

"Each run is walked exactly once, from its starting element. The runs are disjoint — no element belongs to two runs — so their total length is at most n. Every other iteration exits immediately on the contains(n-1) check, which is O(1). So the total work is O(n) set operations, even though the structure looks quadratic."

Why O(n) is the floor. You must examine every element; an adversary could place the longest run anywhere. So O(n) is optimal, and this achieves it.

Honest caveat about hashing. HashSet gives O(1) average, not worst case — adversarial inputs causing mass collisions would degrade it. Java's Integer.hashCode is the identity function, so a malicious input of values spaced exactly by the table size could collide. In practice this never matters, but saying "O(n) expected, assuming good hash distribution" is more precise than a flat O(n).

5. Java Prerequisites

Building the set

Set<Integer> set = new HashSet<>();
for (int n : nums) set.add(n);

Duplicates are dropped automatically — a Set stores each value once, which is exactly what we want since [1,1,2] has a run of length 2, not 3.

Stream alternative:

Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());

boxed() is required: nums is int[] (primitives) and a Set holds objects.

Iterating a Set

for (int n : set) { ... }

Order is arbitrary and may differ between runs. That's fine here — the algorithm is order-independent, since each run is found from its own start regardless of visit order. Say that explicitly; it shows you thought about whether iteration order mattered.

Autoboxing cost

Every set.contains(n + len) boxes the int into an Integer to hash it. That's a real per-operation cost and part of why the theoretically-slower sorting solution can win on small inputs.

Avoiding it needs a primitive-specialized set (fastutil, Eclipse Collections) — worth mentioning, not worth writing.

Integer overflow at the boundary

while (set.contains(n + len)) len++;

If n were Integer.MAX_VALUE, n + len would overflow and wrap negative. Here it's harmless: values are capped at 10^9, and a run long enough to overflow would need 10^9 elements, far beyond n <= 10^5. Worth noting that you checked rather than assuming.

Empty input

if (nums.length == 0) return 0;

The set version handles this naturally — an empty set means the loop never runs and best stays 0. The sorting version needs an explicit guard before touching nums[0].

6. Interview Communication Guide

Clarifying questions

1. "Is O(n) a hard requirement, or is O(n log n) acceptable?" — the problem says O(n), but confirming frames your whole approach.
2. "Can the array contain duplicates?" — yes, and they must not inflate the run length.
3. "Can it be empty?" — return 0.
4. "Does 'consecutive' mean strictly +1 each step?" — yes, integers. No gaps.
5. "Do I need to return the sequence itself, or just its length?" — just the length; returning the values would need the start index tracked.
6. "Can I modify the input?" — matters only for the sorting approach.

The pitch

"Sorting solves this in O(n log n) — sort, then scan for the longest run of consecutive values. But the problem requires O(n), so sorting is out.

What do I actually need? For each number, whether n-1 and n+1 exist anywhere. That's membership, not order — so a HashSet.

The naive version is: put everything in a set, and from each number walk upward while the next value exists. That's correct, but it's secretly O(n²) — on [1..n] I'd walk the whole run from 1, then again from 2, then from 3, and so on.

The fix is one line. I should only start walking from a number that begins a run — and n begins a run exactly when n-1 is not in the set. Everything else gets skipped in O(1).

Now each run is walked exactly once, from its start. The runs are disjoint so their lengths sum to at most n, which makes the total work O(n) — even though the code looks nested.

O(n) time, O(n) space."

Edge cases to raise proactively

[1,2,2,3] is the one to volunteer. It's the case that breaks solutions counting array elements rather than distinct values — a naive counter would say 4. Mentioning it shows you noticed the set gives deduplication for free.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. These are new problems, asked after your solution is accepted — not challenges to it. (Those are the counter-questions attached to each approach in §3.) ⭐ marks the most likely.

"What if you had to return the sequence itself, not just the length?"

Track the starting value alongside the best length. The sequence is then start, start+1, ..., start+len-1 — no need to store the elements.

⭐ "What if the numbers stream in and you must answer at any time?"

Maintain a HashMap<value, runLength> where each run's endpoints store the current length. On inserting x, look up left = map.get(x-1) and right = map.get(x+1), merge into a run of left + right + 1, and update the two new endpoints. O(1) amortized per insertion.

Union-Find also works here, and this is the case where it earns its keep — unlike the offline version.

"What if the values are dense — say all within [0, 10^6]?"

Use a boolean[] indexed by value instead of a hash set. Same algorithm, no hashing or boxing, substantially faster in practice. The reason it's not the default here is the ±10^9 range — that would need two billion slots.

"What about the longest consecutive sequence in a binary tree?"

Different problem entirely — DFS carrying the current run length down from parent to child. The hashing idea doesn't transfer because the structure, not the values, defines adjacency.

"Can you do it in O(1) space?"

Only by sorting, which costs O(n log n) and mutates the input. You cannot have O(n) time and O(1) space here: without order to exploit, you need memory to answer membership questions. Being able to explain that trade-off is worth more than trying to beat it.