ASAPUtils
The signal
“Consecutive integers” plus an explicit O(n) requirement. The O(n) demand is the interesting part: it rules out sorting, which is the only obvious approach, and forces you to find what makes a run identifiable without order.
Approach ladder
1. Sort, then scan — O(n log n)
Sort, walk, count adjacent runs, handle duplicates. Completely correct and explicitly ruled out by the time constraint. Say it anyway — it takes ten seconds and shows you’re not stuck.
2. Set + walk from everything — O(n²) worst case
Put everything in a set, then from each value walk upward while x+1 is present. Correct, but on
[1, 2, 3, …, n] you walk the whole run from every element: n + (n−1) + … = O(n²).
3. What is it wasting?
Re-walking the same run over and over from its middle. The run starting at 1 and the run starting at 2 are the same run — only the first is worth measuring.
4. The insight
Only start counting from a number that starts a run. And x starts a run exactly when x − 1
is not in the set. One extra check, and the quadratic blowup disappears.
int longestConsecutive(vector<int>& a) {
unordered_set<int> s(a.begin(), a.end());
int best = 0;
for (int x : s) {
if (s.count(x - 1)) continue; // not a run start
int len = 1, cur = x;
while (s.count(cur + 1)) { cur++; len++; }
best = max(best, len);
}
return best;
}
function longestConsecutive(a) {
const s = new Set(a);
let best = 0;
for (const x of s) {
if (s.has(x - 1)) continue; // not a run start
let len = 1, cur = x;
while (s.has(cur + 1)) { cur++; len++; }
best = Math.max(best, len);
}
return best;
}
Why the nested loop is still O(n)
This is the part worth being able to say out loud, because it looks quadratic and isn’t:
The inner
whileonly ever runs for a value that starts a run. Each run is therefore walked exactly once in total, no matter how many of its members are in the array. So across the entire execution every element is touched at most twice — once as a candidate start, once inside the one run it belongs to. Total work is O(n).
That’s an amortised argument, and the same shape of reasoning justifies the monotonic stack in week 3. Learning to make it here pays off twice.
Complexity
- Time O(n) — by the argument above.
- Space O(n) — the set.
Traps
- Dropping the run-start check. Still correct, quietly O(n²), and it will time out.
- Iterating the array instead of the set when there are many duplicates. Iterating the set is cleaner and avoids repeated work on duplicates.
- Returning the end value instead of the length.
- Empty input.
bestmust start at 0, not 1.
Blank re-solve prompt
Find the longest run of consecutive integers in an unsorted array, in O(n). Then explain in one sentence why the inner while loop doesn’t make it quadratic.