All patterns
Linear Scan
Arrays & Strings
Beginner
Interactive
Maintain a compact running state while scanning a sequence once.
Time
O(n)
Space
O(1)
ActiveComparingMatch / bestIn windowFrontierVisitedExcludedAnswer
No frames to display.
The idea
A linear scan turns a sequence into one pass by carrying only the state the next element needs. This visualization tracks a running maximum, but the same invariant supports running minima, counts, frequencies, and prefix decisions.
Analogy
A hands-on model of linear scan that exposes every state change instead of hiding it inside a library call.
When to reach for it
- Learning the underlying data structure.
- Tracing state changes and invariants.
- Building a reusable interview template.
Language-independent template
best = arr[0]
for i from 1 to n-1:
best = max(best, arr[i])Complexity — time O(n), space O(1).
Common mistakes
- Skipping boundary checks.
- Updating state in the wrong order.
- Using the structure without preserving its invariant.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Easy
Choose one buy day and a later sell day for maximum profit.
Medium
Build each output without division in linear time.
Hard
Find the smallest absent positive integer in linear time and constant space.
Variations
Change the input and replay the trace.
Adapt the operation to a related interview problem.