Run it
The O(n) version with its inner-loop steps counted against the version missing the start check, on an input built to make the difference obvious.
The sorting solution, for reference
O(n log n), correct, and worth stating first because it establishes the baseline. The set() matters: without it, [1, 1, 2] counts the repeated 1 as extending the run.
The O(n) solution: start only at run starts
Put everything in a set for O(1) membership tests. Then for each number, only begin counting if it is the start of a run — that is, if num - 1 is not in the set.
This looks quadratic — a while loop inside a for loop — and it is O(n). The reason is the continue guard:
Every number is walked over by exactly one inner loop: the one starting at the beginning of its own run. A number in the middle of a run is skipped immediately by the guard, and is visited once as part of its run's single expansion. So the total inner-loop work across the whole outer loop is n, not n per iteration.
Remove the guard and it genuinely becomes O(n²) — [1, 2, 3, ..., n] would expand from every position. That single if is the difference between the intended solution and a slow one, and explaining it is what the interviewer is listening for.
Tracing [100, 4, 200, 1, 3, 2]
| num | num-1 present? | Action | Run found |
|---|
| 1 | No (0 absent) | Expand: 2, 3, 4 present | 4 |
| 2 | Yes (1 present) | Skip | — |
| 3 | Yes | Skip | — |
| 4 | Yes | Skip | — |
| 100 | No | Expand: 101 absent | 1 |
| 200 | No | Expand: 201 absent | 1 |
Six outer iterations, and the inner loop ran a total of six times. The answer is 4.
Iterating over seen rather than nums is a small extra win — duplicates are already collapsed, so [1] * 1000 does one iteration instead of a thousand. Either is O(n); the set is tidier.
Why not just sort
Sorting makes it trivial — one pass counting adjacent runs — and costs O(n log n). The question asks for O(n) specifically to rule that out, so give the sorting answer, name its cost, and then improve it.
The check that makes it linear
Without the start-of-run test, each value walks its whole run and the work is quadratic on a long sequence. With it, a value only walks forward when value - 1 is absent — and each run has exactly one such value.
So across the entire input the inner loop takes as many steps as there are elements, not as many as elements times run length. Every element is touched at most twice: once in the outer loop, once by the walk of its own run.
Saying the complexity convincingly
This is the question where candidates write the right code and then call it O(n²) because there is a loop inside a loop. The argument to make out loud is amortised: the inner loop's total work across all iterations is bounded by n, because runs do not overlap.
Same shape as the sliding window, where both pointers only move forward. A nested loop is not automatically quadratic; what matters is how many times the inner body can run in total.
The union-find alternative
Consecutive numbers can be treated as edges in a graph and merged with a disjoint-set structure, taking the size of the largest component.
Correct, and the wrong answer for this problem — much more code, more memory, and no better asymptotically. Worth knowing only because interviewers sometimes ask "could union-find solve this?", and the right response is "yes, and the set approach is simpler for the same complexity".
| Approach | Time | Space | Verdict |
|---|
| Brute force per element | O(n³) | O(1) | No |
| Sort and scan | O(n log n) | O(n) | Acceptable baseline |
| Hash set with run-start guard | O(n) | O(n) | The answer |
| Union-find | O(n α(n)) | O(n) | Correct, overkill |
| Dictionary of run lengths | O(n) | O(n) | Also O(n), fiddlier |
The dictionary of run lengths variant is worth a mention: as each number arrives, look up the run lengths ending at num-1 and starting at num+1, merge them, and update the boundary entries. It handles a stream of numbers, where the set approach needs all the input up front. That is the answer to "what if the numbers arrive one at a time?"
Edge cases
| Case | Result |
|---|
| Empty array | 0 — max() over nothing raises, so guard it |
| Single element | 1 |
| All duplicates | 1 |
| Negative numbers | Work unchanged — nothing assumes non-negative |
| Already consecutive | len(set(nums)) |
| No two consecutive | 1 |
| Very large values | Fine — the set is keyed on value, not indexed by it |
That last row is the reason a hash set is used rather than a boolean array: [1, 1000000000] would need a billion-entry array and needs a two-entry set.
The empty-array case is the one that actually breaks code, because best = 0 initialised before the loop handles it, while a max(...) generator expression over an empty input raises ValueError.
Longest increasing subsequence. Superficially similar and much harder — O(n log n) with patience sorting, and no hash-set shortcut, because the values need not be consecutive.
Missing ranges / summary ranges. Compress a sorted array into range strings, which is the same run-detection logic.
First missing positive. Also solved with a set, or in O(1) space by using the array itself as a hash table.
Longest consecutive sequence in a binary tree. Same definition, traversed recursively along parent-child paths.
Longest harmonious subsequence. Values differing by at most 1, solved with a Counter.
What it is testing
Do you find the O(n) approach? The sorting solution is the baseline, and the question is asked to see whether you get past it.
Can you explain why the nested loop is linear? This is the real question. Each number is visited by exactly one expansion because non-starts are skipped.
Do you handle duplicates? A set handles them for free; a naive scan double-counts.
Do you guard the empty input? One line, and it is where the solution crashes otherwise.
Do you recognise the amortisation argument? Recognising that total work, not per-iteration work, determines complexity is a transferable skill — the same reasoning justifies the two-pointer and monotonic-stack patterns.
Recap in one screen
- Put the numbers in a set for O(1) membership tests.
- Expand a run only from numbers with no predecessor in the set — that guard is what makes it O(n).
- Total inner-loop work is n, because each number belongs to exactly one run expansion.
- Sorting gives an easy O(n log n) baseline; state it, then improve on it.
- Guard the empty input, and use a set so duplicates cannot inflate a run.