Longest Consecutive Sequence

ARRAYS & HASHING · MEDIUM

The problem

Given an unsorted array of integers nums, find the length of the longest run of consecutive integers that are all present somewhere in the array. The run doesn’t need to be contiguous in the array — only the values themselves need to be consecutive. For example, [100, 4, 200, 1, 3, 2] contains the values 1, 2, 3, 4 scattered across positions 3, 5, 4, and 1 — but since all four are present, that’s a consecutive run of length 4, and it’s the longest one available. The required optimal solution must run in O(n) time.

Solution 1: Brute force — sort, then a single pass

The simplest correct idea: if the values were in order, spotting a consecutive run would just be a matter of walking left to right and checking whether each value is exactly one more than the last. So make that true — sort the array first — then do exactly that single pass, resetting a running counter to 1 every time the gap to the previous distinct value isn’t exactly 1, and explicitly skipping over duplicate values so they don’t get mistaken for a broken run.

Interactive visualization

nums = [100, 4, 200, 1, 3, 2] — sorted ascending, then walk once comparing each to its predecessor

Press Play or Step to begin.

Step 0 / —

This animation traces nums=[100,4,200,1,3,2] — LeetCode’s own canonical example (expected: 4), verified above before any HTML was written.

The code

function longestConsecutiveBrute(nums) {
  if (nums.length === 0) return 0;

  const sorted = nums.slice().sort((a, b) => a - b);
  let longest = 1;
  let current = 1;

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) continue; // duplicate — same value, not a gap
    if (sorted[i] === sorted[i - 1] + 1) {
      current++;
    } else {
      current = 1; // gap — restart the run here
    }
    longest = Math.max(longest, current);
  }
  return longest;
}

Line by line:

nums.length === 0 is handled up front — an empty array has no run at all, length 0, and every index below assumes at least one element exists.
nums.slice().sort((a, b) => a - b) — sorts ascending numerically (the default sort without a comparator would stringify values, so 10 would sort before 2). .slice() keeps the caller’s original array untouched.
if (sorted[i] === sorted[i - 1]) continue; — duplicates sit adjacent after sorting but represent the same value, not forward progress. This isn’t a cosmetic optimization: skip it and see the trap in Interview Corner below.
sorted[i] === sorted[i - 1] + 1 — the actual consecutive check: only a gap of exactly 1 extends the run; anything else (a gap of 2+) resets current back to 1, because a brand-new potential run starts at sorted[i].
longest = Math.max(longest, current) runs every iteration so the best run seen so far is always captured, even if a later, shorter run follows it.

Complexity

Time	Space	Approach
O(n log n)	O(n)	Sort dominates; assumes a typical engine’s `Array.prototype.sort` (e.g. V8’s TimSort, which is not in-place and needs O(n) auxiliary space) — an in-place O(log n)-space quicksort variant exists in other languages, but it isn’t what actually runs here

Solution 2: Optimal — hash set with sequence-start detection

Put every value into a Set for O(1) average membership checks. The key trick: only start counting a run from a value v if v - 1 is not in the set. If v - 1 is present, v can’t be the start of anything — it’s the middle (or end) of a run that some smaller value already owns, and that smaller value will (or already did) count it. Once a genuine start is found, walk forward — v + 1, v + 2, … — while each is in the set, tracking how long the run gets.

Interactive visualization

nums = [100, 4, 200, 1, 3, 2] — build Set, then for each distinct value check if it's a sequence start

Press Play or Step to begin.

Step 0 / —

Same nums=[100,4,200,1,3,2] as Solution 1, so step counts are directly comparable. Distinct values are shown sorted left to right purely for visual clarity — a real Set iterates in insertion order, and correctness never depends on the order values are visited in.

The code

function longestConsecutiveOptimal(nums) {
  const set = new Set(nums);
  let longest = 0;

  for (const v of set) {
    if (set.has(v - 1)) continue; // not a sequence start — some smaller value owns this run

    let length = 1;
    let cur = v;
    while (set.has(cur + 1)) {
      cur++;
      length++;
    }
    longest = Math.max(longest, length);
  }
  return longest;
}

Line by line:

new Set(nums) — O(n) to build, and duplicates collapse for free: a value either is or isn’t in the set, its count doesn’t matter for this problem.
for (const v of set) visits every distinct value exactly once, in whatever order the Set stores them (insertion order in JS — never assume sorted order here).
if (set.has(v - 1)) continue; — the whole trick. If a smaller value one less than v exists, v is guaranteed to be counted by that smaller value’s forward walk instead, so starting a redundant walk from v too would be wasted work.
The inner while (set.has(cur + 1)) loop only ever runs starting from a confirmed sequence start — see the amortized-cost interview question below for exactly why that keeps the total work linear despite the loop looking nested inside the for.
longest = Math.max(longest, length) updates once per completed run, not once per element — cheap relative to the walk itself.

Complexity

Time	Space	Approach
O(n) amortized	O(n)	Hash set membership + sequence-start detection bounds every element to being walked forward at most once across the entire algorithm

Complexity comparison

Solution	Time	Space
Brute force (sort + single pass)	O(n log n)	O(n)
Optimal (hash set + sequence-start check)	O(n) amortized	O(n)

This is a real, honest time improvement — O(n log n) down to O(n) — not just a different technique at the same complexity. Both use O(n) extra space (a sorted copy of the array for Solution 1, a hash set for Solution 2), so the space cost is a wash; the win is purely in time, and it comes from replacing the sort’s ordering guarantee with O(1) average hash lookups that don’t need any ordering to detect adjacency.

Interview corner

The inner while loop is nested inside the outer for loop — doesn’t that make this O(n²) in the worst case, like a naive nested loop would?

It looks nested, but the outer loop’s if (set.has(v - 1)) continue; check means the inner while loop only ever actually runs starting from a genuine sequence start — a value with no smaller neighbor in the set.
Across the entire array, every value can be the start of at most one run (its own), and every value can only ever be walked past by the inner loop once — as part of the one run it belongs to.
Summed over the whole algorithm, the total number of inner-loop iterations across every outer-loop pass is bounded by the total number of distinct values, n — not n restarts of an n-length walk. That’s what “amortized O(n)” means here: the cost is spread evenly across all elements, not concentrated per-element.

Solution 1 needs a sort to detect adjacency. Why doesn’t Solution 2 need any ordering at all?

Sorting exists in Solution 1 purely to make “is there a value one more than this one?” answerable by just looking at the next array position — an indirect substitute for a direct lookup.
A hash Set gives that lookup directly: set.has(v + 1) is O(1) average, regardless of what order values were inserted in.
Since the optimal solution never needs to ask “what’s next in sorted order,” it never needs the array to be sorted (or even iterated in any particular order) in the first place.

In Solution 1, is if (sorted[i] === sorted[i - 1]) continue; just a performance nicety, or does skipping it actually break correctness?

It’s required for correctness, not just tidiness. Consider nums = [1, 2, 2, 3] — sorted, that’s [1, 2, 2, 3].
Without the duplicate check, at i = 2 the comparison is sorted[2] === sorted[1] + 1, i.e. 2 === 3 — false. The code would treat the duplicate as a gap and wrongly reset current back to 1.
That produces a final answer of 2 instead of the correct 3 (verified directly: removing the duplicate check on this exact input yields 2, not 3) — the duplicate would be silently mistaken for a break in the run instead of a repeat of a value already counted.

Trick question — what does this log?

const set = new Set([-0]);
console.log(1 / [...set][0]);

Answer: Infinity, not -Infinity — even though -0 was the value inserted.
Set (and Map) use the SameValueZero algorithm for equality, which treats -0 and +0 as the same value for membership purposes — that part is well known.
Less well known: when a JS engine stores -0 in a Set, it canonicalizes it to +0 on the way in — so reading the value back out gives +0, and 1 / 0 is Infinity, not 1 / -0’s -Infinity. Verified directly: Object.is([...new Set([-0])][0], -0) is false; Object.is(..., 0) is true.

⚠️ Trap: This is exactly why new Set(nums) in the solution above is safe to reason about with plain ===-style thinking for ordinary integers, but would be a subtle footgun for a variant of this problem that allowed floating-point input containing both 0 and -0 as “different” sentinel values — a Set silently treats them as one and the same.

Quiz

1. In the optimal solution, why does the algorithm skip starting a forward walk from any value v where v - 1 is also in the set?

Correct answer: v can’t be the start of its run — a smaller value already owns (or will own) counting it, so walking from v too would be redundant work.

Explanation: If v - 1 is in the set, v is guaranteed to be part of a run that starts at some smaller value. That smaller value’s forward walk will count v as part of its run, so starting a redundant walk from v too would waste time and not change the final answer.

Other options:

It’s a minor performance tweak with no effect on correctness or the overall time complexity — No, this is the core trick that makes amortized O(n) possible.
Sets in JavaScript refuse to iterate values that have a smaller neighbor already inserted — No, Sets iterate in insertion order and have no such mechanism.

2. The inner while loop is nested inside the outer for loop. Why is the overall time still O(n) instead of O(n²)?

Correct answer: Every value can only ever be walked forward past once, across the entire algorithm, because the while loop only runs from confirmed sequence starts — total work is bounded by n.

Explanation: The amortized argument: each element is visited at most once by an inner-loop pass. Even though the while loop is visually nested, the sequence-start check ensures it only runs starting from legitimate run beginnings. Across the whole algorithm, each value is counted at most once, so total iterations sum to O(n).

Other options:

The while loop is hard-capped at a fixed number of iterations regardless of input — No, the loop length varies with the data.
The JavaScript engine automatically optimizes nested loops over Sets into O(n) at runtime — No, this is a logical guarantee from the algorithm, not a runtime optimization.

3. In the brute-force solution, is if (sorted[i] === sorted[i - 1]) continue; required for correctness, or just a performance optimization?

Correct answer: Required — without it, a duplicate is wrongly treated as a gap and the run counter incorrectly resets, producing a wrong final answer.

Explanation: Without the duplicate skip, nums = [1, 2, 2, 3] would produce a final answer of 2 instead of 3. The second 2 would fail the +1 gap test and trigger a reset, breaking the run incorrectly.

Other options:

Optional — it only saves a few comparisons, the final answer is identical either way — No, tested directly and this causes wrong answers.
Required — without it, comparing equal values throws a runtime error — No, the comparison succeeds; it just produces a wrong result.

4. Why doesn’t the optimal solution need to sort nums at all, when the brute-force solution’s entire strategy depends on sorting first?

Correct answer: A Set’s O(1) average has() check directly answers “is v+1 present?” — the exact question sorting exists to make answerable in the brute-force version.

Explanation: Sorting in Solution 1 is a means to an end: making “is the next integer here?” answerable by array indexing. A hash Set provides that answer directly, making the sort redundant.

Other options:

LeetCode guarantees nums arrives pre-sorted for this specific problem — No, the input is explicitly unsorted.
Sorting would actually make the optimal solution faster too, it’s just skipped for simplicity — No, adding a sort would only slow it down.

5. What’s the honest complexity difference between the two solutions?

Correct answer: A genuine time improvement — O(n log n) down to O(n) — with both solutions using the same O(n) space.

Explanation: Solution 1 is bottlenecked by the sort’s O(n log n) work. Solution 2 replaces that with O(1) hash lookups. Space is O(n) in both cases (sorted copy in Solution 1, hash set in Solution 2), so the win is purely in time.

Other options:

The optimal solution trades away space savings to get O(n) time — it actually uses less memory than the brute force — No, both use O(n) space.
Both solutions are actually O(n) — the difference is only in constant factors, not asymptotic complexity — No, O(n log n) and O(n) are genuinely different asymptotic classes.