Course4all

Candy Distribution

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Greedy.

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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMeeting Rooms II
Next Question →Minimum Cost to Connect Sticks