Arrays and Hashing
14 / 170Arrays and HashingLesson 9 of 10About 44 min
The unit's climax. A loop that looks quadratic and is not, because of one guard.
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.
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.
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?
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?
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.