Incremental computation is the practice of maintaining state as you move through a problem, instead of recomputing it from scratch on each step.
It’s the reason many linear-time algorithms beat their nested-loop counterparts. The outer structure looks the same — one pass over the input — but each step updates existing state in O(1) rather than rebuilding it in O(n).
The skill is asking what is the smallest piece of state I need to carry forward, and finding an update rule that maintains exactly that.
A few examples:
- Sliding window sum: instead of recomputing
sum(window)on each step, add the new element and subtract the one that fell off. - Remove duplicates in-place: instead of deleting (which shifts everything), overwrite forward with a write pointer.
- Kadane’s algorithm: instead of tracking every subarray sum, track only “best ending here” — a single number carries all the state you need.
TIP
Whenever you write a loop inside a loop, ask: do I actually need to recompute this, or can I update what I already have?