Longest Consecutive Sequence

Learning goal: Recognize what must be measured and why an unsorted input makes the problem interesting.

Core idea We want the length of the longest set of values that can be ordered as x, x + 1, x + 2, and so on. The original order does not matter, and duplicates should not increase a streak's length. The challenge is to avoid repeatedly sorting or scanning the entire array for every possible starting value.

Algorithm plan

• Read the values from nums.
• Treat membership as the important operation: is x present?
• For each distinct value, decide whether it is the beginning of a run.
• Count forward only from genuine beginnings and keep the largest count.

Micro-example For nums = [100, 4, 200, 1, 3, 2], the run 1, 2, 3, 4 has length 4. Values 2, 3, and 4 belong to that run but should not restart it.

Pitfalls

• The input is not sorted, so adjacent positions are not adjacent values.
• Duplicate values should be collapsed by a set.
• Returning the largest numeric value instead of the largest run length answers a different question.

Recap

• Measure consecutive values, not consecutive input positions.
• Distinct membership is more useful than input order.
• The intended solution avoids sorting.

Learning goal: Understand why checking for a missing left neighbor prevents redundant work.

Core idea A value x can begin a consecutive run only when x - 1 is absent from the set. If x - 1 exists, then x is already inside a run whose beginning lies to the left, so counting from x would duplicate work. This single boundary check converts a tempting nested scan into an expected O(n) algorithm.

Algorithm plan

• Build values = set(nums).
• For each x in values, test whether x - 1 is missing.
• If so, repeatedly test x + 1, x + 2, and later values.
• Update best with the length of the run.

Micro-example For the set {1, 2, 3, 4}, only 1 starts a count because 0 is absent. Values 2, 3, and 4 are skipped as starts because their left neighbors exist.

Pitfalls

• Starting from every x causes the same streak to be recounted many times.
• Checking x + 1 before confirming x - 1 is absent loses the linear-time guarantee.
• A set lookup is expected O(1), not a scan through the array.

Recap

• A missing left neighbor identifies a run boundary.
• Count rightward only from boundaries.
• The set supplies constant-time membership checks.

Learning goal: Translate the boundary idea into a reliable procedure and justify its complexity.

Core idea The set stores every distinct number, so membership checks do not depend on the array's order. Each valid start launches one forward walk; because a number can be reached only from the beginning of its run, the total number of successful forward checks is linear in the number of distinct values.

Algorithm plan

1. Create values = set(nums).
2. Initialize best = 0.
3. For each x in values, continue only if x - 1 is absent.
4. Set length = 1 and current = x.
5. While current + 1 is in values, advance and increment length.
6. Set best = max(best, length) and return best.

values = set(nums)
best = 0
for x in values:
    if x - 1 not in values:
        current, length = x, 1
        while current + 1 in values:
            current += 1
            length += 1
        best = max(best, length)
return best

Micro-example At x = 1, the missing neighbor 0 proves this is a start. The walk finds 2, 3, and 4, producing length = 4.

Pitfalls

• Set iteration order is arbitrary; correctness must not depend on it.
• Initialize best to 0 so an empty input works.
• Do not remove values during the walk unless the proof and implementation are redesigned.

Recap

• Boundary check, then rightward walk.
• best records the longest completed run.
• Expected time is O(n) and space is O(n).

Learning goal: Trace the set-based algorithm on one complete input and connect each decision to the invariant.

Core idea Use nums = [100, 4, 200, 1, 3, 2], the first example. The set is {1, 2, 3, 4, 100, 200}. We inspect each distinct value, but only values without a left neighbor launch a walk. The order in which the set yields values does not affect the final answer.

Algorithm plan

• Build the set once.
• For 100, 99 is absent, so its run has length 1.
• For 4, 3 exists, so skip it as a start.
• For 200, 199 is absent, so its run has length 1.
• For 1, 0 is absent; walk through 2, 3, and 4 to obtain length 4.
• Skip 3 and 2 because their left neighbors exist.

Micro-example The important walk is 1 → 2 → 3 → 4 → stop. At every point, best is the longest run found so far, ending at 4.

Pitfalls

• Do not confuse “visited during a walk” with “removed from the set.”
• A failed lookup ends a run; it is not an error.
• Values such as 100 and 200 are valid one-element runs.

Recap

• The set contains six distinct values.
• Only 100, 200, and 1 launch walks in this trace.
• The final maximum is 4.

Learning goal: Identify common incorrect approaches and verify the boundary cases that the set solution handles naturally.

Core idea Sorting followed by a linear scan is correct, but it costs O(n log n) and misses the intended O(n) set-based trick. The set method also needs careful treatment of duplicates, empty input, and isolated values. The start condition is the central correctness guard: a run must be counted from its smallest present value.

Algorithm plan

• Convert to a set to ignore duplicates.
• Check x - 1 before entering the inner loop.
• Let the inner loop stop naturally when current + 1 is absent.
• Return 0 when there are no values.

Micro-example For nums = [1, 2, 2, 3], the set is {1, 2, 3} and the answer is 3, not 4. For nums = [], no starts exist, so best remains 0.

Pitfalls

• Sorting (O(n log n)) is acceptable, but it misses the intended O(n) set-based trick that starts only from run beginnings.
• Counting from every value can become quadratic on a long streak.
• Treating duplicates as separate steps overcounts the sequence.
• Using an array search instead of a set makes each lookup O(n).

Recap

• Duplicates do not extend a run.
• Empty input returns 0.
• The predecessor test is both an optimization and the key invariant.

Learning goal: Explain why the nested-looking loops still achieve expected linear time and retain the solution pattern for future problems.

Core idea The outer loop examines each distinct value once. The inner loop does not restart at every value: it runs only from a sequence beginning, and each element in that sequence is encountered during that one forward walk. Across all runs, each distinct element is involved in at most a constant number of checks, giving expected O(n) time. The set stores up to n distinct values, so space is O(n).

Algorithm plan

• Build the set: expected O(n).
• Test each value as a possible start: expected O(n) total.
• Walk each run once from left to right: expected O(n) total.
• Track only the maximum length and return it.

Micro-example For [100, 4, 200, 1, 3, 2], six values enter the outer consideration, but only three values start walks. The long run is counted once, not four times.

Pitfalls

• “Nested loop” does not automatically mean O(n^2); analyze how often the inner loop can revisit values.
• Expected O(1) set operations rely on a hash-set implementation.
• Do not claim O(1) space because only best is stored; the set is required.

Recap

• Time: expected O(n).
• Space: O(n).
• General pattern: use a hash set and expand only from boundaries.