Classic Greedy

Candy Distribution

Each child gets at least 1 candy. A child with a higher rating than a neighbor must get more candies. Two passes: left-to-right (handle right-neighbor constraint), right-to-left (handle left-neighbor). Take the max.

O(n)

How It Works

Candy distribution gives each child at least one candy while any child rated higher than an immediate neighbor must receive more candies than that neighbor. The two constraints (left neighbor, right neighbor) are decoupled into two sweeps. Left to right: if ratings[i] > ratings[i-1], set candy[i] = candy[i-1] + 1, satisfying all left constraints. Right to left: if ratings[i] > ratings[i+1], raise candy[i] to at least candy[i+1] + 1. Taking the max of the two passes satisfies both directions simultaneously, and each value is the minimum possible.

The result is O(n) time with an O(n) candy array; a more intricate one-pass variant tracks ascending and descending run lengths for O(1) extra space. Splitting bidirectional constraints into two directional sweeps is a broadly reusable trick.

Step-by-Step Visualization

Ratings [1,0,2]. Each child gets ≥1 candy

Initial[1, 1, 1]

1/3

Code

Java

static int candy(int[] ratings) {
  int n = ratings.length;
  int[] candies = new int[n];
  Arrays.fill(candies, 1);

  for (int i = 1; i < n; i++)
    if (ratings[i] > ratings[i-1]) candies[i] = candies[i-1] + 1;

  for (int i = n-2; i >= 0; i--)
    if (ratings[i] > ratings[i+1]) candies[i] = Math.max(candies[i], candies[i+1] + 1);

  int sum = 0;
  for (int c : candies) sum += c;
  return sum;
}

Tips & Gotchas

1Two passes: left-to-right (compare with left neighbor)

2Right-to-left (compare with right neighbor)

3Take max of both passes for each child

Practice Problems

1Candy
2Trapping Rain Water
3Product of Array Except Self
4Minimum Number of Coins for Fruits

About the Classic Greedy Pattern

Standard problems where the greedy approach has an elegant proof of correctness.

Key insight

Greedy is NOT 'try the obvious thing'. It works only when local optimality guarantees global optimality. Sort first (by end time, deadline, ratio), then pick greedily. If greedy fails, try DP.

Common Greedy Interview Problems

Jump Game
Activity Selection
Meeting Rooms II
Gas Station
Candy
Task Scheduler
Partition Labels

Frequently Asked Questions

Why can't a single left-to-right pass handle both constraints?

A long strictly decreasing run means each child's candy depends on children to the right that a forward pass has not seen yet. The backward pass resolves exactly those descending stretches, and taking the maximum reconciles positions governed by both directions, such as local peaks.

How do equal adjacent ratings behave?

Equal neighbors impose no constraint in either direction, so a child rated the same as a neighbor can legitimately receive just one candy. Treating equality like 'greater' inflates the total and is the most common wrong answer on plateau-heavy inputs.

Where else does the two-pass max trick apply?

Trapping Rain Water uses prefix and suffix maxima from both directions, and Product of Array Except Self multiplies prefix and suffix products. Whenever each position's answer combines independent left-side and right-side information, two opposing sweeps merged per index give O(n) solutions.