Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Turn ranges into boundary events: The Population Ledger.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Difference-array sweep matches the clues
- 2Keep this true after every move: after processing year y, active equals the population alive during y
- 3Reach the result within O(n + year range)
Rules and pressure
- Target cost: O(n + year range)
- State rule: after processing year y, active equals the population alive during y
Lesson 1 of 3
Live algorithm trace
Difference-array sweep
Complete execution1 of 7
Record a positive event at each birth and a negative event at each exclusive death.
1
events[birth] += 12
events[death] -= 13
active = 04
scan years in order5
active += events[year]6
update answer only when active > best7
return earliest best yearevents = 1993:+1, 1999:-1, 2000:+1, 2010:-1
Truth to preserve / Cost target
Truth to preserve
after processing year y, active equals the population alive during y
Cost target
O(n + year range)
A person contributes from birth through the year before death. Add one at birth, subtract one at death, then prefix-sum years to recover population and keep the earliest maximum.
Your call · What should guide every step of this algorithm?