The One Line That Makes Longest Consecutive Sequence Linear

Here is the accepted solution to LeetCode 128, and the line this article is about:

const longestConsecutive = (nums) => {
  const numSet = new Set(nums);
  let maxLength = 0;
 
  for (const num of numSet) {
    if (!numSet.has(num - 1)) {          // <-- this one
      let currentNum = num;
      let currentLength = 1;
 
      while (numSet.has(currentNum + 1)) {
        currentNum++;
        currentLength++;
      }
 
      maxLength = Math.max(maxLength, currentLength);
    }
  }
 
  return maxLength;
};

Delete the if. Re-indent. Run your tests.

They pass. Every single one of them, including the tricky ones, including the ones you'd write specifically to catch an off-by-one. I fuzzed the guarded and unguarded versions against a sort-then-scan oracle over 24,000 random arrays — heavy duplicates, negatives spanning zero, values scattered across a billion-wide range — and got zero disagreements. The guard contributes nothing to the answer.

It contributes the complexity class. That is an awkward kind of code to maintain, because nothing in your test suite protects it, and the reason it exists lives entirely in your head.

Removing it

Take the shuffled integers 0 through n - 1 — one long run, no duplicates — and time both versions.

Both columns returned the same answer at every size. The left one doubles when n doubles. The right one roughly quadruples.

// measure.mjs — Node 22, run with: node measure.mjs
const longestConsecutiveNoGuard = (nums) => {
  const numSet = new Set(nums);
  let maxLength = 0;
  for (const num of numSet) {
    let currentNum = num;
    let currentLength = 1;
    while (numSet.has(currentNum + 1)) { currentNum++; currentLength++; }
    maxLength = Math.max(maxLength, currentLength);
  }
  return maxLength;
};
 
const shuffle = (a) => {
  for (let i = a.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
};
 
const time = (fn, arg, reps) => {
  const t = process.hrtime.bigint();
  for (let i = 0; i < reps; i++) fn(arg.slice());
  return Number(process.hrtime.bigint() - t) / 1e6 / reps;
};
 
for (const n of [1000, 2000, 4000, 8000, 16000, 32000]) {
  const a = shuffle(Array.from({ length: n }, (_, i) => i));
  const reps = n <= 4000 ? 20 : 5;
  console.log(n, time(longestConsecutive, a, reps), time(longestConsecutiveNoGuard, a, reps));
}

Wall clock is circumstantial, though. It confounds the algorithm with Set internals, cache behaviour and whatever the JIT felt like doing. The thing worth counting is iterations of the inner while.

Counting the walk

Add a counter to the body of the while and run both shapes over the same input.

const countInner = (nums, useGuard) => {
  const set = new Set(nums);
  let inner = 0;
  for (const n of set) {
    if (useGuard && set.has(n - 1)) continue;
    let c = n;
    while (set.has(c + 1)) { c++; inner++; }
  }
  return inner;
};

On the run 0 .. n-1:

511,984,000 is exactly n(n-1)/2. Without the guard, every element of a run starts its own walk to the end of that run, and you have rebuilt the triangular sum by hand. The guard admits exactly one element per maximal run into the while — the one whose predecessor is missing — so the total inner work across the whole outer loop is the sum of the run lengths, which is the number of distinct values.

I checked that bound over 20,000 random arrays — dense, sparse, duplicate-heavy, mixed — comparing inner iterations against the number of distinct values. Zero inputs exceeded it. The worst ratio observed was 0.976, on an array of 350 elements holding 41 distinct values.

You'll sometimes read that the walk is cheap because visited numbers get "marked as already counted." They don't. The set is never written to after it is built, and there is no seen-set, no deletion, no bookkeeping of any kind. Nothing in the program knows that 2 was already stepped over. The bound is a counting argument about which elements are allowed to enter the loop, not about state the loop maintains — which is exactly why deleting the guard leaves every answer intact.

Instrumenting the lookups themselves puts a number on the other half of it. Wrapping numSet.has in a probe counter gives 2.00 probes per distinct value on every shape I tried: dense runs, isolated singletons, two disjoint runs. One probe from the outer has(num - 1), one from whichever walk steps onto it (or fails to).

Where the O(1) goes soft

Two probes per element only buys you linear time if a probe is constant. Hash lookup is amortised constant, and both words carry weight.

Measured cost of a single has on a Set of packed integers, 4,096 random hits timed in a loop:

Flat it is not — 2.4x across that range, which is cache hierarchy rather than asymptotics, and it is the kind of constant that decides whether your submission times out. The "amortised" part shows up on the write side. Timing every individual add while building a 1,000,000-element Set, the slowest single insert took 6.8 ms, at insert number 524,288. That is 2^19, and it is the backing table doubling. Mean insert cost is a fraction of a microsecond; one insert in the middle costs more than the rest of the build.

And the sorting solution's usual selling point does not survive measurement either:

const longestConsecutiveSorted = (input) => {
  if (input.length === 0) return 0;
  const nums = [...input];              // the original mutates its argument
  nums.sort((a, b) => a - b);
  let maxLength = 1;
  let currentLength = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) continue;
    else if (nums[i] === nums[i - 1] + 1) maxLength = Math.max(maxLength, ++currentLength);
    else currentLength = 1;
  }
  return maxLength;
};

Two things there. The copy on line three is mine; the version everybody writes calls nums.sort() on the caller's array and hands it back reordered. And Array.prototype.sort is not in-place in V8 — it is TimSort, with a work array. Sampling process.memoryUsage().heapUsed from inside the comparator (a setInterval can't help you here, since sort never yields the event loop) while sorting 4,000,000 integers, heap use went from 33.8 MiB to a peak of 98.0 MiB. That is 64.2 MiB of extra space, about 16.8 bytes per element. Calling the sorting approach "O(1) extra space" describes an algorithm, not this runtime.

There is also a range precondition nobody states. Feed the set version [Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER + 1, Number.MAX_SAFE_INTEGER + 2] and it never returns. Past 2^53, x + 1 === x + 2 in IEEE-754 doubles, so currentNum++ stops advancing while numSet.has(currentNum + 1) keeps answering true. The while spins forever on a three-element array. LeetCode's constraints keep values inside ±10^9, which is why nobody trips on it, and why it will be a production incident the day somebody feeds this function IDs from a system that hands out large integers.

Restoring it, and the version you'd have written instead

So the guard goes back in. The remaining question is where else you might put it, because there is a variant that looks equivalent and gets recommended as such: iterate the original array rather than the set.

const longestConsecutiveOverArray = (nums) => {
  const numSet = new Set(nums);
  let maxLength = 0;
 
  for (const num of nums) {            // nums, not numSet
    if (!numSet.has(num - 1)) {
      let currentNum = num;
      let currentLength = 1;
      while (numSet.has(currentNum + 1)) { currentNum++; currentLength++; }
      maxLength = Math.max(maxLength, currentLength);
    }
  }
 
  return maxLength;
};

The guard is present and correct. The Set still does the deduplication that matters for the answer. Fuzzing it against the oracle over the same 24,000 arrays produced zero disagreements, so no test you write will object.

Now build [0, 0, 0, ..., 0, 0, 1, 2, ..., k-1] — k copies of zero, then the run:

Every duplicated 0 passes the guard, because -1 genuinely isn't in the set, and each one walks the entire run to the end. The guard filters on membership; it cannot filter on multiplicity, and the array — unlike the set — hands it the same starting value k times. Iterating numSet is not a tidiness preference over iterating nums. It is the second half of the same argument, and without it the function is quadratic in the duplicate count while returning the right number the whole way down.

That is the failure mode worth remembering from this problem. Both mistakes — dropping the if, and looping the array — are invisible to correctness testing, cost nothing at interview-sized inputs, and only announce themselves as a timeout on a judge or a p99 in production. If you want a regression test that actually holds the line, assert on the counter, not the answer.