Course4all
Join us on telegram
Home/dsa/Greedy/Candy Distribution

Candy Distribution

Master this topic with zero to advance depth.

Candy Distribution

Each child has a rating. You must give candies such that:

  • Every child gets at least 1 candy.
  • Children with a higher rating get more candies than their neighbors.

Return the minimum total candies.

Visual Representation

Ratings: [1, 0, 2] Pass 1 (L->R): [1, 0, 2] -> [1, 1, 2] (fixes child at index 2 rank > index 1) Pass 2 (R->L): [1, 0, 2] -> [2, 1, 2] (fixes child at index 0 rank > index 1) Total: 5
Hard

Examples

Input: ratings = [1,0,2]
Output: 5

Candies: [2, 1, 2]. Total = 5.

Approach 1

Level I: Brute Force (Iterative Satisfaction)

Intuition

Repeatedly scan the ratings and candies. If a child has a higher rating than a neighbor but doesn't have more candies, give them one more. Repeat until no more changes are needed.

Thought Process

  1. Initialize candies with 1 for all.
  2. In a loop, keep track if any changes were made (changed = false).
  3. For each child i:
    • If ratings[i] > ratings[i-1] and candies[i] <= candies[i-1], set candies[i] = candies[i-1] + 1, changed = true.
    • Same for i+1.
  4. Stop when changed is false.
⏱ O(N^2) in the worst case (e.g., strictly increasing ratings).💾 O(N)

Detailed Dry Run

ratings=[1,2,3], initial=[1,1,1] Pass 1: [1,2,1] (i=1), [1,2,3] (i=2). changed=true. Pass 2: No changes. Total=6.

java
public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < n; i++) {
                if (i > 0 && ratings[i] > ratings[i-1] && candies[i] <= candies[i-1]) {
                    candies[i] = candies[i-1] + 1; changed = true;
                }
                if (i < n - 1 && ratings[i] > ratings[i+1] && candies[i] <= candies[i+1]) {
                    candies[i] = candies[i+1] + 1; changed = true;
                }
            }
        }
        int sum = 0; for (int c : candies) sum += c; return sum;
    }
}
Approach 2

Level II: Peak and Valley (Single Pass)

Intuition

We can think of the ratings as a sequence of mountains (peaks) and valleys. The number of candies increases as we climb a mountain from a valley, and decreases as we descend. The 'peak' child gets the maximum needed from both sides.

Thought Process

  1. Use variables up, down, and peak to track the current mountain slopes.
  2. If rating increases, up++, down=0, peak=up. Candies += up + 1.
  3. If rating decreases, down++, up=0. Candies += down.
  4. If down > peak, we need to add one extra candy to the peak to keep it higher than the descending slope.

Pattern: Slope Analysis

⏱ O(N)💾 O(1)

Detailed Dry Run

ratings = [1, 2, 1]

  • i=1 (up): up=1, peak=1, candies = 1 + (1+1) = 3.
  • i=2 (down): down=1, up=0. down <= peak (1 <= 1). candies = 3 + 1 = 4. Sum = 4? Wait, [1, 2, 1] should be [1, 2, 1] -> 4. Correct.
java
public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        if (n <= 1) return n;
        int candies = 1, up = 0, down = 0, peak = 0;
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                up++; down = 0; peak = up; candies += 1 + up;
            } else if (ratings[i] == ratings[i - 1]) {
                up = 0; down = 0; peak = 0; candies += 1;
            } else {
                down++; up = 0; candies += down + (down > peak ? 1 : 0);
            }
        }
        return candies;
    }
}
Approach 3

Level III: Optimal Greedy (Two Independent Passes)

Intuition

A child must satisfy two conditions: candies[i] > candies[i-1] if ratings[i] > ratings[i-1], and candies[i] > candies[i+1] if ratings[i] > ratings[i+1]. We can solve these separately.

Thought Process

  1. Start all children with 1 candy.
  2. L-to-R: If rating[i] > rating[i-1], set candies[i] = candies[i-1] + 1.
  3. R-to-L: If rating[i] > rating[i+1], set candies[i] = max(candies[i], candies[i+1] + 1).

Pattern: Constraint Satisfaction in Multiple Passes

⏱ O(N) - Two passes.💾 O(N) for candies.

Detailed Dry Run

ratings = [1, 2, 8, 7, 3, 4, 1] L->R: [1, 2, 3, 1, 1, 2, 1] R->L: [1, 2, 3, 2, 1, 2, 1] Result: 12

java
public class Solution {
    public 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;
    }
}
← Previous QuestionMeeting Rooms II
Next Question →Minimum Cost to Connect Sticks