Keeping score at a cricket match: you don't rewatch every ball, you just update the runs, wickets and best partnership after each one.
Clues that point here
→ "Maximum/minimum so far"
→ Best profit from buying before selling
→ Answer depends only on a summary of the past, not every past element
→ O(n) time and O(1) space expected
Not this pattern when
✕ The answer needs to look back at arbitrary earlier positions (hash map or prefix sums)
✕ Elements interact in pairs across the array (two pointers, sorting)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Running State in One Pass · template
int best = Integer.MIN_VALUE;
int summary = initialValue; // e.g. the minimum price seen so far
for (int x : arr) {
best = Math.max(best, score(x, summary)); // use the past summary
summary = update(summary, x); // then fold x into it
}
return best;