Maximum, minimum and top-k questions where the answer can be updated incrementally.
- largest or smallest seen so far
- one result from an unsorted input
- sorting feels unnecessary
The running variables contain the best valid answer for the prefix already processed.
Usually O(n) time. Typical auxiliary space: Usually O(1).
JAVA STARTING POINT
A template to adapt, not memorize.
int best = values[0];
for (int index = 1; index < values.length; index++) {
best = Math.max(best, values[index]);
}Common mistakes
- Using zero as the initial answer
- Updating dependent answers in the wrong order
- Ignoring duplicate rules
PUBLISHED / 02
Learn in this order.
Available articles always appear before the publishing plan.
Find the Largest Element in an Array
Learn to keep a running maximum, reason about each comparison, and trace a one-pass Java solution.
Read article →Find the Second Largest Element in an Array
Track the two largest distinct values in one pass without sorting the array.
Read article →PLANNED PRACTICE
What comes after the published lessons.
- Third largest distinct valuePlanned, not yet published
- Best time to buy and sell stockPlanned, not yet published
