Arrays and Hashing
Only count from the start of a run
The unit's climax. A loop that looks quadratic and is not, because of one guard.
The situation
A set of values contains runs: stretches where each value is one more than the last. In {100, 4, 200, 1, 3, 2} there are three runs, namely 1-2-3-4, then 100, then 200.
Any question about those runs has the same trap in it, and the trap is worth meeting on an easy version before you meet it on a hard one.
The natural first idea
For each value, walk upward while the next value is present. That correctly identifies the run each value sits in.
Written naively it is O(n squared). Take the input 1, 2, 3, ..., n. Starting from 1 you walk n steps. Starting from 2 you walk n - 1. Every element re-walks the whole rest of its run.
Why it works
The guard that fixes it
Only start walking from a value that begins a run. A value v begins a run exactly when v - 1 is absent from the set.
One condition, and each run gets walked once in total rather than once per member. Here it is used to count how many runs there are, which needs no walking at all, just the test.
Cost
Why the guard changes the complexity
With the guard, the outer loop still runs once per distinct value, O(n) iterations. Any inner walking only happens for values that start a run.
Add the inner steps across the whole outer loop. Each element is stepped over by exactly one run's walk, the run containing it, and only once. So the inner work totals O(n) across the entire loop rather than O(n) per iteration. The whole thing is O(n) time and O(n) space.
Bounding total work across all iterations, rather than the work of any single one, is called amortized analysis. It returns for sliding windows in Unit 3 and monotonic stacks in Unit 4, where the same nested-loop-that-is-secretly-linear shape appears.
Tip
Iterate the set, not the original list
Looping over the set rather than the input matters when there are many duplicates. With a million copies of one number, looping over the input does a million outer iterations and looping over the set does one. It does not change the worst case, it is free, so do it.
Edge cases
Cases to check
The empty input. A single element. Heavy duplicates, which must not inflate anything. Negative numbers, which work unchanged because nothing here assumes positivity.
Decide what each should produce before you write the problem below, because two of them are where an otherwise correct attempt usually fails.
What to take from this unit
Every problem here was the same move in a different costume: stop recomputing something by remembering it. A set remembers what you have seen. A counter remembers how often. A canonical key remembers what things have in common. A prefix array remembers a running total. A run-start guard remembers that a run has already been counted.
When you meet an unfamiliar problem, the question that most reliably makes progress is still the one from Unit 0: what is this recomputing, and what could I remember instead?
What does the guard actually buy?
Suppose you are measuring the longest run rather than counting runs, so each starting value walks upward while the next value is present. What happens if you drop the value - 1 not in values guard and walk from every value?
Longest Consecutive Sequence
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.