Longest Consecutive Sequence

Introduction

An unsorted array of integers arrives, and the question is: what is the longest run of consecutive values — possibly scattered throughout the array — that together cover an interval with no gaps?

The obvious move is to sort and scan. It works in $O(n \log n)$ and is the answer most candidates produce. What makes this problem an interview favorite is that there is a better answer — one with amortized $O(n)$ time — and reaching for it requires the right move at the right time. That move is: build a hash set, then only walk forward from chain heads (values x whose predecessor x − 1 is not in the set). Skipping non-heads is what keeps the nested loop from being quadratic.

The trick isn’t the hash set. It’s knowing which elements NOT to start walking from.

If you can’t see immediately why the chain-head filter saves the asymptote, read the amortized analysis in the recommended approach — it’s the whole interview signal. If you can, skip to the union-find treatment: it’s the third lens and it matters when the input is streaming.

What the interviewer is actually testing

1. Willingness to move past the first idea. Candidates who sort and scan, state $O(n \log n)$, and stop are giving the right answer with the wrong complexity. The test is whether you explicitly ask “can we do better?” even after finding a correct solution.
2. The chain-head insight. The move from “walk from every element” to “walk only from chain heads” is non-obvious. Naming it out loud — “I’ll start only from values whose predecessor is absent” — is the signal.
3. Amortized reasoning. The hash-set approach has a nested loop and looks like it could be $O(n^2)$. Explaining why it’s not — each element is visited at most twice total across all walks — separates mid-level candidates from senior ones.
4. Tool selection. Knowing when union-find is the right tool (streaming updates, merging regions) versus when it’s overkill (static one-shot) is the senior signal.

Problem statement

Clarifying questions — and why each one matters

A mental framework — sort is the obvious move; asking “can I do better” is the signal

If the array were sorted, the problem is trivial: walk the array once, tracking a running-length counter that resets whenever the gap between consecutive sorted values isn’t exactly 1. That gives $O(n \log n)$ for the sort plus $O(n)$ for the scan — a correct and clean solution.

The question an interviewer hopes you’ll ask yourself is: do we actually need the elements sorted, or do we just need to know which values are present? Sorting is a strong tool with a lot of information; this problem only needs set membership — “is value y somewhere in the input?”. That’s the $O(1)$ operation a hash set gives you.

Once you have $O(1)$ membership, the shape of the algorithm becomes: for each starting value x, walk forward through x + 1, x + 2, ... as long as each is in the set. The longest walk wins.

The trap: a naive version runs that walk from every starting value. On the input [1, 2, 3, ..., n], starting from 1 walks through all n, starting from 2 walks through n − 1, and so on — $O(n^2)$ worst case. The fix is the chain-head filter in the recommended approach.

Discussion

#include <algorithm>
#include <vector>

int longestConsecutive(std::vector<int> nums) {
    if (nums.empty()) return 0;
    std::sort(nums.begin(), nums.end());
    nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
    int best = 1;
    int run = 1;
    for (std::size_t i = 1; i < nums.size(); ++i) {
        if (nums[i] == nums[i - 1] + 1) {
            ++run;
            if (run > best) best = run;
        } else {
            run = 1;
        }
    }
    return best;
}

#include <unordered_set>
#include <vector>

int longestConsecutive(const std::vector<int>& nums) {
    std::unordered_set<int> present(nums.begin(), nums.end());
    int best = 0;
    for (const int x : present) {
        // Start a walk only from chain heads (x - 1 not present).
        // This keeps the inner loop from repeating work already covered
        // by a walk that started at a smaller member of the same chain.
        if (present.count(x - 1)) continue;
        int length = 1;
        for (int y = x + 1; present.count(y); ++y) ++length;
        if (length > best) best = length;
    }
    return best;
}

#include <unordered_map>
#include <utility>
#include <vector>

class DSU {
  public:
    void add(int x) {
        if (parent_.count(x)) return;
        parent_[x] = x;
        size_[x] = 1;
        if (best_ < 1) best_ = 1;
    }

    bool contains(int x) const { return parent_.count(x) > 0; }

    int find(int x) {
        while (parent_[x] != x) {
            parent_[x] = parent_[parent_[x]];
            x = parent_[x];
        }
        return x;
    }

    void unite(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return;
        if (size_[ra] < size_[rb]) std::swap(ra, rb);
        parent_[rb] = ra;
        size_[ra] += size_[rb];
        if (size_[ra] > best_) best_ = size_[ra];
    }

    int best() const { return best_; }

  private:
    std::unordered_map<int, int> parent_;
    std::unordered_map<int, int> size_;
    int best_ = 0;
};

int longestConsecutive(const std::vector<int>& nums) {
    DSU dsu;
    for (const int x : nums) {
        dsu.add(x);
        if (dsu.contains(x - 1)) dsu.unite(x, x - 1);
        if (dsu.contains(x + 1)) dsu.unite(x, x + 1);
    }
    return dsu.best();
}

Approach comparison

Default answer: hash set with chain-head filter. Name the amortized argument out loud when you close.

Follow-ups to anticipate

Pattern recognition — amortized walks on set membership

The move this chapter teaches — build a hash set; walk forward from filtered starting points so each element is touched a bounded number of times — is a staple of amortized linear-time algorithms. Places it reappears:

• Next Greater Element (monotonic stack). Each element is pushed and popped at most once; total work is $O(n)$ despite a nested loop shape.
• Sliding Window Maximum. A monotonic deque touches each element at most twice — once on entry, once on exit.
• Kth Largest in Stream. Amortized analysis on heap size bounds the work per insertion.
• Longest Increasing Subsequence (patience sort). Binary search per element over a bounded-size sorted pile; total $O(n \log n)$ by amortized argument.
• Find-all-duplicates-in-O(1)-space. The index-placement trick visits each element at most twice via a cyclic-swap argument.

The reflex: when a nested loop looks quadratic but “most” inner iterations are short, ask whether each element can be bounded by a constant number of total visits. If yes, the algorithm is amortized linear even though no single iteration proves it.

What to say out loud — the delivery script

Ten beats:

1. “Let me restate: given an unsorted array, return the length of the longest consecutive-integer subsequence.”
2. Ask: “duplicates allowed? how large is n? streaming or one-shot?”
3. “The obvious solution sorts and scans — $O(n \log n)$. Let me name it, then try to beat it.”
4. “We don’t need the elements sorted; we just need to know which values are present. That’s a hash set, $O(1)$ membership.”
5. “With the set, I can walk forward from each value. But walking from every value is $O(n^2)$ on a long run. I need to restrict starting points.”
6. “Only walk from chain heads: values $x$ where $x − 1$ is not in the set. That guarantees each chain is traversed once.”
7. Write the code — eight lines. Point at the continue and say: “this is the load-bearing line.”
8. “Complexity argument: outer loop is $O(n)$; total inner-walk work sums to $n$ across all chains; total $2n = O(n)$.”
9. Trace example 1 on the whiteboard. Show that $\{1, 2, 3, 4\}$ produces exactly one walk from 1, and that 2, 3, 4 all skip.
10. “For a streaming variant I’d switch to union-find. For a bounded-range variant I’d use a bitset. For the static problem, this hash-set approach is what I’d ship.”

Summary

Longest Consecutive Sequence looks like a sort-and-scan problem and turns out to have a linear-time answer that hinges on a single filter: only walk from chain heads. The insight — don’t start walking from values whose predecessor is already in the set — is what converts a naive nested loop into amortized linear work.

The wider lesson is the amortized-analysis reflex. Nested loops are not automatically quadratic. When each element is bounded in the number of total visits, the algorithm is linear no matter how the loops nest. That reflex unlocks the hash-set filter here, the monotonic-stack trick in next-greater-element, the sliding-window-max deque, and half a dozen other ”$O(n)$ in disguise” patterns across the interview canon.