The array state pattern: how to spot it
Updated
Many array problems are solved in one pass by carrying a little state forward instead of looking back: the best value so far, a running minimum, a write index, or prefix and suffix products. The skill is choosing what to remember.
When to reach for it
- A brute force compares each element with everything before or after it.
- The answer depends on the best or worst value seen so far.
- You must change the array in place, keeping some elements' order.
- Each position needs a combination of everything to its left and right.
The usual shape
best = worst_possible
state = initial # running min, write index, prefix product…
for x in items:
best = better(best, combine(state, x))
state = update(state, x)
return best5 LeetCode arrays problems, easiest first
- Best Time to Buy and Sell Stock easy
Track the cheapest buy behind you. Profit is price minus that min.
- Merge Sorted Array easy
Write from the end so you do not clobber unread values in nums1.
- Move Zeroes easy
Write pointer keeps the next non-zero. Zeros fill the tail.
- Rotate Array medium
k wraps with modulo. Reverse-three-times or extra buffer both count.
- Product of Array Except Self medium
Left products times right products. No division; zeros make division illegal.
check which skills you have 10 minutes, free, no account.