Two-Pass Greedy · bigonotes

Some rules involve both neighbors of an element: "a child with a higher rating than a neighbor gets more candy". Trying to satisfy both sides in one sweep goes wrong, because you don't yet know what the right side needs. A two-pass greedy splits the rule in half: one pass handles the left neighbor, a second pass handles the right, and you combine the two.

The idea#

Break a two-sided constraint into two one-sided ones.

Left to right: satisfy every "compared with the left neighbor" rule, using the minimum each element needs.
Right to left: satisfy every "compared with the right neighbor" rule, raising values only when needed (max of the two).

It works because each pass gives the smallest value that meets its side's rule. Taking the max of both meets both rules, and nothing smaller could, since dropping below either pass's value breaks that side.

How to spot it#

These signals in a question point to a two-pass greedy.

A rule about both neighbors: "more than its neighbors", "taller than both sides".
A one-directional sweep works for half of the cases but breaks on a decreasing run.
Answers built from "everything to the left" and "everything to the right" (products, maxes, last positions).

Template#

Start every element at the smallest allowed value. Each pass raises values only as far as its own rule needs.

value = smallest allowed value for every element
for i from 1 to n - 1:                 # left rule
    if element i must beat element i - 1:
        value[i] = value[i - 1] + 1
for i from n - 2 down to 0:            # right rule, keep the left rule
    if element i must beat element i + 1:
        value[i] = max(value[i], value[i + 1] + 1)
combine the values (sum, max, ...)

Each pass is $O(n)$ , so the whole thing is $O(n)$ .

A trace#

To see the two passes work together, here is the template on the Candy rule: "every value is at least 1, and an element with a higher rating than a neighbor gets a bigger value than that neighbor".

ratings	after left pass	after right pass	total
`[1, 0, 2]`	`[1, 1, 2]`	`[2, 1, 2]`	5
`[1, 3, 4, 5, 2]`	`[1, 2, 3, 4, 1]`	`[1, 2, 3, 4, 1]`	11

Pitfalls#

These mistakes cause the most wrong answers.

Overwriting in the second pass instead of taking the max. That breaks the left rule you already satisfied.
Trying a single pass with look-ahead. Long decreasing runs force you to go back and fix earlier values.
Adding constraints the rule doesn't state. A "strictly higher" rule puts no constraint on equal neighbors.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Candy

Everyone starts with one candy. The left pass handles a higher rating than the left neighbor, and the right pass does the same for the right neighbor with max. Equal ratings get no extra candy.

Hint: Partition Labels

Here the first pass only records facts: each letter's last occurrence. The second pass walks the string and stretches the current part's end to the last occurrence of every letter it sees. Close the part when the index reaches that end.

Hint: Product of Array Except Self

The same two-sweep shape: one pass collects the product of everything to the left, the other multiplies in everything to the right. See Prefix/Suffix Aggregates.

Hint: Shortest Distance to a Character

One pass left to right records the distance to the last c seen. A second pass right to left does the same from the other side, keeping the smaller of the two.

Key takeaways#

Split a two-sided rule into a left pass and a right pass.
Each pass gives the minimum its side requires; combine with max.
A first pass can also collect facts (last positions) for the second pass to use.

Core idea#

Split a rule about both neighbors into two one-sided rules. Sweep left to right for the left rule, then right to left for the right rule, and combine with max.

Key points#

Each pass gives the smallest value that meets its side's rule.
The max of both meets both rules, and nothing smaller can.
Spot it: "more than its neighbors", or a one-way sweep that breaks on a decreasing run.
Partition Labels: the first pass records each letter's last occurrence. The second pass stretches the part's end and closes it when the index reaches the end.
Product of Array Except Self has the same shape: a left product pass and a right product pass.

Template#

value = smallest allowed value for every element
for i from 1 to n - 1:                 # left rule
    if element i must beat element i - 1:
        value[i] = value[i - 1] + 1
for i from n - 2 down to 0:            # right rule, keep the left rule
    if element i must beat element i + 1:
        value[i] = max(value[i], value[i + 1] + 1)
combine the values

Pitfalls#

Overwriting in the second pass instead of taking the max. That breaks the left rule.
A single pass with look-ahead. Long decreasing runs force you to fix earlier values.
Giving equal ratings more candy. The rule is strictly "higher".

Say it in an interview#

"One pass handles the left neighbor, one handles the right, and max combines them."