Two-pass greedy
Meet rules that look at both neighbors by sweeping once from the left for the left-side rule and once from the right for the right-side rule, then combining.
O(n)Space O(n)5 practice problemsStep-through pictureThe idea
Some rules compare each item with both of its neighbors. A classic one: people stand in a line with scores, everyone gets at least one reward point, and anyone with a higher score than a neighbor must get more points than that neighbor. One left-to-right pass can't see the right neighbors, and fixing one side can break the other.
The two-pass trick splits the rule in two. A left-to-right pass makes sure everyone beats their left neighbor when they should: if scores[i] > scores[i - 1], give rewards[i] = rewards[i - 1] + 1. A right-to-left pass then handles the right neighbor: if scores[i] > scores[i + 1], raise rewards[i] to at least rewards[i + 1] + 1.
Each pass gives the smallest values that satisfy its own side. Taking the larger of the two at each position satisfies both sides while staying as small as possible. The same pattern finds the distance to the nearest marker, the water above each bar of a chart, and which way falling dominoes lean.
An everyday example
Handing out stickers along a line of kids
Kids stand in a line holding test scores. A teacher walks from the left end, giving each kid one more sticker than the kid on their left if they scored higher, or just one sticker otherwise. Then a second teacher walks from the right end and checks each kid against the kid on their right, adding stickers only where needed. Neither teacher alone gets it right, but together they do, with no wasted stickers.
| In the example | In the code |
|---|---|
| The kids' scores | scores |
| Stickers each kid holds | rewards |
| The first teacher walking from the left | for (let i = 1; i < n; i++) |
| The second teacher walking from the right | for (let i = n - 2; i >= 0; i--) |
| Adding only the stickers that are missing | Math.max(rewards[i], rewards[i + 1] + 1) |
From the slow way to two-pass greedy
- A first try: give everyone
1point, then scan the line and fix every broken rule by raising a value. One fix can break the rule next to it, so scan again, and again, until a whole scan changes nothing. On a falling run like[9, 7, 5, 3, 1], each scan only settles one more person, so it takes 5 scans of 5 people:O(n^2)in general. - Split each person's rule in two. The left rule says: if your score beats your left neighbor's, you need more points than them. The right rule says the same about your right neighbor. The left rule only looks left, so one left-to-right scan settles it: when you reach
i, the value ati - 1is already final. - The right rule is the mirror image. One right-to-left scan settles it, because when you reach
i, the value ati + 1is already final. Each scan alone gives the smallest values that satisfy its own rule. - Run the left scan first and keep its values. Then run the right scan, but at each
itake the larger of the value you have and what the right rule needs:Math.max(rewards[i], rewards[i + 1] + 1). Raising a value can't break a left rule that already holds. That pair of loops is the two-pass greedy.
How it works
- Give every item the smallest allowed value:
rewardsfilled with1. - Left-to-right pass: for
ifrom1, ifscores[i] > scores[i - 1], setrewards[i] = rewards[i - 1] + 1. - Now every item beats its left neighbor where it must.
- Right-to-left pass: for
ifromn - 2down to0, ifscores[i] > scores[i + 1], setrewards[i] = Math.max(rewards[i], rewards[i + 1] + 1). - Taking the max keeps the left-side rule while fixing the right side.
- Add up
rewardsand return the total.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function minRewards(scores) {const n = scores.length;const rewards = new Array(n).fill(1);for (let i = 1; i < n; i++) {if (scores[i] > scores[i - 1]) rewards[i] = rewards[i - 1] + 1;}for (let i = n - 2; i >= 0; i--) {if (scores[i] > scores[i + 1]) {rewards[i] = Math.max(rewards[i], rewards[i + 1] + 1);}}return rewards.reduce((sum, reward) => sum + reward, 0);}
How fast it is
| Time | O(n) |
|---|---|
| Extra memory | O(n) |
Two passes with constant work per item, plus one final sum. The rewards array stores one number per item.
- Best case
O(n)Any input, even equal scores like
[5, 5, 5]: both passes always visit every item, about3nsteps with the final sum. - Average case
O(n)Random scores: two passes and a sum, with constant work per item.
- Worst case
O(n)A long falling run like
[9, 7, 5, 3, 1]: the right pass raises every value, but each raise is still one step.
Common mistakes
- Doing only one pass, which breaks on a falling run like
[3, 2, 1]. - Overwriting in the second pass (
rewards[i] = rewards[i + 1] + 1) instead of taking the max, which can lower a value the left pass needed. - Running the second pass left to right, so it reads values that aren't final yet.
- Giving equal neighbors more rewards. The rule is only about strictly higher scores, so equal neighbors can have any counts.
When to use it
Look for these clues in a problem:
- Each item's value depends on its left neighbor and its right neighbor.
- The question asks for the minimum total that satisfies rules with neighbors, like rewards, ratings, or heights.
- For each position you need something about the nearest or largest item on each side.
- A one-direction pass gives right answers for one side but breaks the other.
Check yourself
Answer each one in your head first, then open it.
Why must the second pass go from right to left?
It reads rewards[i + 1], which must already be final. Going right to left fixes i + 1 before i. Going left to right, a falling run like [3, 2, 1] would read values that still need to rise.
What goes wrong if the second pass writes rewards[i] = rewards[i + 1] + 1 instead of using Math.max?
It can lower a value the left pass needed. In the trace, index 3 would drop from 4 to 2, below index 2's 3, even though 9 > 6.
Do two neighbors with equal scores ever need different points?
No. The rule only applies to strictly higher scores, so equal neighbors can have any values, and the code leaves them alone.
What is the total for scores = [2, 4, 6, 8], and why?
10. The left pass gives [1, 2, 3, 4], and the right pass changes nothing, because no score beats its right neighbor.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingGo further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
After the left pass, this rule holds for every i: if scores[i] > scores[i - 1], then rewards[i] > rewards[i - 1]. Each step sets rewards[i] from a left neighbor that won't change again in that pass, so once the pass ends, the rule holds for every pair. Each value is the length of the rising run that ends at i, and any valid answer needs at least that much.
The right pass keeps a second rule as it moves from right to left: after it handles i, if scores[i] > scores[i + 1], then rewards[i] > rewards[i + 1]. It moves right to left, so rewards[i + 1] is already final when i reads it. And it only ever raises values, never lowers them.
Raising never breaks the left rule. The pass raises rewards[i] only when scores[i] > scores[i + 1], so there's no left rule between i and i + 1 to break, and the left rule between i - 1 and i only gets easier when rewards[i] goes up. The right rule for i - 1 is checked next, after rewards[i] is final. Each final value is the larger of two lower limits that any valid answer must meet, so the total is the smallest possible.
Going deeper
3 more ideas
Why taking the larger value is both correct and smallest
After the first pass, rewards[i] is the smallest value that satisfies the left-side rule; call it L[i]. The second pass on its own would give the smallest value for the right-side rule, R[i]. Any valid answer must give position i at least L[i] and at least R[i], so at least Math.max(L[i], R[i]). The two passes give exactly that, and it satisfies both rules, so it's the smallest valid total.
Why the right pass must go right to left
When the second pass looks at i, it uses rewards[i + 1], which must already be final. Going from right to left makes sure position i + 1 was fixed first. Going left to right would use values that might still go up, and a long falling run like [5, 4, 3, 2, 1] would come out wrong.
Why it takes O(n) time
Two passes over n items with constant work each is O(n). The rewards array uses O(n) memory. Some two-pass problems can be done with one pass and two pointers, like the water over a bar chart, but the two-pass version is often easier to get right.
Work it by hand
Every step in a table, with why
Give the fewest reward points to 7 people. The scores rise to a peak, fall, and have two equal scores side by side.
scores = [1, 4, 6, 9, 5, 5, 2]
| Step | Pass | i | Check | rewards | What happens | Why |
|---|---|---|---|---|---|---|
| 1 | start | - | - | [1, 1, 1, 1, 1, 1, 1] | everyone gets 1 | Each person must get at least one point. |
| 2 | left | 1 | 4 > 1 | [1, 2, 1, 1, 1, 1, 1] | rewards[1] = 2 | Index 1 beats its left neighbor, so it gets one more than it. |
| 3 | left | 2 | 6 > 4 | [1, 2, 3, 1, 1, 1, 1] | rewards[2] = 3 | The rising run continues. |
| 4 | left | 3 | 9 > 6 | [1, 2, 3, 4, 1, 1, 1] | rewards[3] = 4 | The peak ends a rising run of four, so it gets 4. |
| 5 | left | 4 | 5 > 9 is false | [1, 2, 3, 4, 1, 1, 1] | no change | Index 4 is lower than its left neighbor, so the left rule asks nothing of it. |
| 6 | left | 5 | 5 > 5 is false | [1, 2, 3, 4, 1, 1, 1] | no change | Equal scores: the rule only asks for more when a score is strictly higher. |
| 7 | left | 6 | 2 > 5 is false | [1, 2, 3, 4, 1, 1, 1] | no change | The left pass is done. Every left rule now holds. |
| 8 | right | 5 | 5 > 2 | [1, 2, 3, 4, 1, 2, 1] | Math.max(1, 1 + 1) = 2 | Index 5 beats its right neighbor, so it rises to 2. |
| 9 | right | 4 | 5 > 5 is false | [1, 2, 3, 4, 1, 2, 1] | no change | Index 4 stays at 1 even though index 5 has 2, because equal scores need no order. |
| 10 | right | 3 | 9 > 5 | [1, 2, 3, 4, 1, 2, 1] | Math.max(4, 1 + 1) = 4 | The right rule only needs 2 here, but the left pass already gave 4. Math.max keeps 4; writing 2 would break the rule against index 2. |
| 11 | right | 2 | 6 > 9 is false | [1, 2, 3, 4, 1, 2, 1] | no change | Index 2 is lower than its right neighbor. |
| 12 | right | 1 | 4 > 6 is false | [1, 2, 3, 4, 1, 2, 1] | no change | No change. |
| 13 | right | 0 | 1 > 4 is false | [1, 2, 3, 4, 1, 2, 1] | no change | The right pass is done. Every right rule now holds too. |
| 14 | sum | - | - | [1, 2, 3, 4, 1, 2, 1] | total 14 | reduce adds the values: 1 + 2 + 3 + 4 + 1 + 2 + 1. |
It returns 14. Every higher score beats each lower neighbor, and no value can go down without breaking a rule.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Two-pass greedy | O(n) | O(n) | Each item's rule looks at both neighbors, and each side can be settled by one scan. |
| Assign in order of score | O(n log n) | O(n) | Handle people from lowest to highest score and give each one more than any lower neighbor already has. It's correct and easy to argue, but the sort makes it slower. |
| One pass counting slopes | O(n) | O(1) | Only the total is needed and memory is very tight. The code is harder to get right. |
| Repeat fix-up scans | O(n^2) | O(n) | Never needed, but it explains why one pass isn't enough. |
Extra memory: O(n) for rewards. If you only need the total, a version that counts the lengths of rising and falling slopes needs O(1) memory, but it is much harder to get right.
How the steps grow
- Two-pass greedy, One pass counting slopes
O(n) - Assign in order of score
O(n log n) - Repeat fix-up scans
O(n^2)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Two-pass greedy | 10 | 1,000 | 1 million |
| Assign in order of score | 33 | 9,966 | 20 million |
| One pass counting slopes | 10 | 1,000 | 1 million |
| Repeat fix-up scans | 100 | 1 million | 1 trillion |
Inputs that need care
5 tricky inputs
- No people:
scores = [] rewardsis empty, both loops are skipped, andreducewith the start value0returns0.- One person:
scores = [42] - Both loops are skipped and it returns
1. - All equal:
scores = [3, 3, 3, 3] - No score is strictly higher than a neighbor, so everyone keeps
1and it returns4. - A falling run:
scores = [9, 7, 5, 3, 1] - The left pass changes nothing. The right pass builds
[5, 4, 3, 2, 1]from the right, for a total of15. - A peak with a longer left side:
scores = [1, 2, 3, 8, 2] - The left pass gives the peak
4; the right pass would only need2.Math.maxkeeps4, and the total is1 + 2 + 3 + 4 + 1 = 11.
Variations and follow-ups
Twists interviewers add
Distance to the nearest marker
For each position in a string, find the distance to the nearest X. A left pass records the distance to the last X seen on the left, a right pass does the same from the right, and you keep the smaller of the two. It has the same shape, with Math.min instead of Math.max.
Water above a bar chart
A left pass records the tallest bar so far from the left, and a right pass from the right. The water above bar i is Math.min(leftMax[i], rightMax[i]) - height[i]. A two-pointer version does it in one pass with O(1) memory.
Product of all the others
For each index, find the product of every other item without dividing. A left pass stores the product of everything before i, and a right pass multiplies in everything after i. Again, each pass sees one side.
Falling dominoes
In a row of dominoes pushed left or right, a left-to-right pass records how far each domino is from the last push to the right, and a right-to-left pass does the same for pushes to the left. The nearer push wins, and a tie keeps the domino standing.
In an interview
Spot it, explain it, answer follow-ups
- Spot it when a rule ties each item to both neighbors: "more than its neighbors", "nearest on either side", "blocked from the left and the right". If information from one direction settles half the rule, think two passes.
- Explain it as two smaller problems: "first I satisfy every left rule, then every right rule, and taking the max keeps the first while fixing the second". Then say why the second pass must go right to left.
- Test by hand: one item, all equal scores, and a peak whose left side is longer than its right side. The peak is where
Math.maxmatters. - The usual follow-up is "can you do it with
O(1)extra memory?". Yes, by counting the lengths of rising and falling slopes and adding triangle numbers, but say that the two-pass version is clearer and easier to prove.
Where frontend code uses it
The same idea in real UI code
- Computing, for each character in a text field, the distance to the nearest space or cursor marker, with one pass from each side.
- Laying out a row of cards where each card must be at least as tall as its neighbors require, such as smoothing a skyline of bar heights in a chart.
- Text editors find the word around the cursor by scanning left to the previous separator and right to the next one. Doing this for every position at once is a left pass and a right pass.