On this page
Description
Array traversal means one pass over the elements while you keep some running state: a total, a smallest value, a count. It's the simplest array technique, and most of the others build on it. This skill makes that single pass automatic. You'll pick the right starting value, decide what an empty array should return, and learn when one pass isn't enough.
We'll go from simple to more technical:
- The pattern: one loop and one running value.
- Tracking more than one value in the same pass.
- Where the same shape appears in production code.
- The two edge cases that break it: empty input and the wrong starting value.
The approach
Keep one variable that holds the answer so far. Start it at a value that can't distort the result, then update it once per element. For a sum, start at 0. For a maximum, start from the first element, not from 0.
Here's why 0 is wrong for a maximum. Find the largest value in [-4, -2, -7, -1]:
| After reading | Starting from the first element | Starting from 0 |
|---|---|---|
| -4 | -4 | 0 |
| -2 | -2 | 0 |
| -7 | -2 | 0 |
| -1 | -1 | 0 |
The right answer is -1. Starting from 0 returns 0, a value that isn't even in the array.
Java
int findMax(int[] nums) {
if (nums.length == 0) throw new IllegalArgumentException("empty array");
int best = nums[0]; // the first element, never 0
for (int i = 1; i < nums.length; i++) {
best = Math.max(best, nums[i]);
}
return best;
}
Python
def find_max(nums: list[int]) -> int:
if not nums:
raise ValueError("empty list")
best = nums[0] # the first element, never 0
for x in nums[1:]:
best = max(best, x)
return best
Every one-pass question has this shape. Only the starting value and the update change: 0 and + for a sum, the first element and max for a maximum, 0 and +1 for a count.
A second flavor: more than one running value
Some questions need two values from the same pass, such as the smallest and the largest. Keep one variable for each and update both inside the same loop. You still read every element once. "Two separate passes" and "one pass with two variables" are both O(n), but the second reads the data only once, which matters when the data comes from a stream.
Where you'll see it
Summing today's orders as they come out of a database cursor is the same loop. You keep one running total, and you see each row exactly once. A stream like that is often too big to hold in memory and can't be read twice. That's why "running state only" is worth getting comfortable with.
Which tool for which job?
| You need | Use |
|---|---|
| One number from the whole array (sum, min, max, count) | a single pass with an accumulator |
| Answers about many sub-ranges | prefix sums |
| Something about a contiguous window | a sliding window |
| Pairs from both ends | two pointers |
| A running total you can't hold in memory | the same pass over a stream |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
Starting a max at 0 | an all-negative array reports 0 | start from the first element (or the identity, -inf) |
Starting a min at 0 | an all-positive array reports 0 | start from the first element (or +inf) |
| Ignoring the empty array | a crash, or a made-up answer | decide: error, sentinel or Optional/None |
Summing large ints in a Java int | silent overflow | accumulate in a long |
| A fancier structure for a one-number question | extra code and memory | one pass is optimal |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. A function that finds the maximum starts with max = 0. What's wrong, and when does it show up?
Show answer
When every element is negative, it returns 0, a value that was never in the array. On ordinary inputs with at least one non-negative number it works. That's why the bug can ship unnoticed.
2. Why is Optional<Integer> often a better return type for "find the minimum" than a plain int?
Show answer
An int can't say "there is no answer". Any value you pick for that, such as 0 or -1, could also be a real minimum. The caller can't tell "the minimum is -1" from "the array was empty". Optional.empty() makes the missing case explicit.
3. Two pointers, sliding windows and Kadane's algorithm are all "a single pass with extra bookkeeping". What's the extra bookkeeping?
Show answer
More than one running value, updated by rules that fit the problem. Two pointers keep two indexes. A sliding window keeps its two edges and a running total of what's inside. Kadane's keeps the best sum ending here and the best sum overall. The single pass itself doesn't change.
Key takeaways
- One pass with one running value (sum, min, max, count) is O(n) time and O(1) space.
- The starting value must not distort the answer: 0 for a sum, the first element for a max or min.
- Decide what empty input returns: an error,
Optional/None, or a documented value. - Most other array techniques are this same pass with more values tracked.