Candy

Distribute the minimum number of candies to children in a line such that each child gets at least one and children with higher ratings get more than their neighbors

Language Selection

Choose your preferred programming language

Showing: Python

Candy

Problem Statement

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating than their neighbor must get more candies than that neighbor.

Return the minimum number of candies you need to have to distribute the candies to the children.

Constraints:

  • n == ratings.length
  • 1 <= n <= 2 * 10^4
  • 0 <= ratings[i] <= 2 * 10^4

Examples:

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate [2,1,2] candies to the first, second, and third child respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate [1,2,1] candies. The third child gets 1 candy because the requirement
only applies when a child has a strictly higher rating than a neighbor.

Example 3:

Input: ratings = [1,3,2,2,1]
Output: 7
Explanation: You can allocate [1,2,1,2,1] candies.

Example 4:

Input: ratings = [1,2,3,4,5]
Output: 15
Explanation: Strictly increasing ratings: [1,2,3,4,5] candies.

Approach 1: Brute Force (Iterative Adjustment)

Algorithm:

  1. Give every child 1 candy initially
  2. Repeatedly scan the array and fix violations (where a higher-rated child has fewer or equal candies compared to a neighbor)
  3. Continue until no more violations exist
  4. This converges because each adjustment only increases candy counts

Time Complexity: O(n^2) in the worst case Space Complexity: O(n)

Python:

def candy(ratings):
    """
    Distribute minimum candies using iterative adjustment
    Time: O(n^2)
    Space: O(n)
    """
    n = len(ratings)
    candies = [1] * n

    changed = True
    while changed:
        changed = False
        for i in range(n):
            # Check left neighbor
            if i > 0 and ratings[i] > ratings[i - 1] and candies[i] <= candies[i - 1]:
                candies[i] = candies[i - 1] + 1
                changed = True
            # Check right neighbor
            if i < n - 1 and ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
                candies[i] = candies[i + 1] + 1
                changed = True

    return sum(candies)

Java:

class Solution {
    /**
     * Distribute minimum candies using iterative adjustment
     * Time: O(n^2)
     * Space: O(n)
     */
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        java.util.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 total = 0;
        for (int c : candies) {
            total += c;
        }
        return total;
    }
}

Go:

// candy - Distribute minimum candies using iterative adjustment
// Time: O(n^2)
// Space: O(n)
func candy(ratings []int) int {
    n := len(ratings)
    candies := make([]int, n)
    for i := range candies {
        candies[i] = 1
    }

    changed := true
    for changed {
        changed = false
        for 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
            }
        }
    }

    total := 0
    for _, c := range candies {
        total += c
    }
    return total
}

JavaScript:

/**
 * Distribute minimum candies using iterative adjustment
 * Time: O(n^2)
 * Space: O(n)
 */
function candy(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);

    let changed = true;
    while (changed) {
        changed = false;
        for (let 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;
            }
        }
    }

    return candies.reduce((sum, c) => sum + c, 0);
}

C#:

using System;
using System.Linq;

public class Solution {
    /// <summary>
    /// Distribute minimum candies using iterative adjustment
    /// Time: O(n^2)
    /// Space: O(n)
    /// </summary>
    public int Candy(int[] ratings) {
        int n = ratings.Length;
        int[] candies = new int[n];
        Array.Fill(candies, 1);

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

        return candies.Sum();
    }
}

Approach 2: Two-Pass Greedy (Optimal)

Algorithm:

  1. Initialize every child with 1 candy
  2. Left-to-right pass: If ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1 (satisfy left neighbor constraint)
  3. Right-to-left pass: If ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1) (satisfy right neighbor constraint while preserving left constraint)
  4. Sum all candies for the answer

Time Complexity: O(n) Space Complexity: O(n)

Python:

def candy(ratings):
    """
    Distribute minimum candies using two-pass greedy
    Time: O(n)
    Space: O(n)
    """
    n = len(ratings)
    if n <= 1:
        return n

    candies = [1] * n

    # Left-to-right: satisfy left neighbor constraint
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    # Right-to-left: satisfy right neighbor constraint
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)

    return sum(candies)

Java:

class Solution {
    /**
     * Distribute minimum candies using two-pass greedy
     * Time: O(n)
     * Space: O(n)
     */
    public int candy(int[] ratings) {
        int n = ratings.length;
        if (n <= 1) return n;

        int[] candies = new int[n];
        java.util.Arrays.fill(candies, 1);

        // Left-to-right: satisfy left neighbor constraint
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Right-to-left: satisfy right neighbor constraint
        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 total = 0;
        for (int c : candies) {
            total += c;
        }
        return total;
    }
}

Go:

// candy - Distribute minimum candies using two-pass greedy
// Time: O(n)
// Space: O(n)
func candy(ratings []int) int {
    n := len(ratings)
    if n <= 1 {
        return n
    }

    candies := make([]int, n)
    for i := range candies {
        candies[i] = 1
    }

    // Left-to-right: satisfy left neighbor constraint
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            candies[i] = candies[i-1] + 1
        }
    }

    // Right-to-left: satisfy right neighbor constraint
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            if candies[i+1]+1 > candies[i] {
                candies[i] = candies[i+1] + 1
            }
        }
    }

    total := 0
    for _, c := range candies {
        total += c
    }
    return total
}

JavaScript:

/**
 * Distribute minimum candies using two-pass greedy
 * Time: O(n)
 * Space: O(n)
 */
function candy(ratings) {
    const n = ratings.length;
    if (n <= 1) return n;

    const candies = new Array(n).fill(1);

    // Left-to-right: satisfy left neighbor constraint
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }

    // Right-to-left: satisfy right neighbor constraint
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }

    return candies.reduce((sum, c) => sum + c, 0);
}

C#:

using System;
using System.Linq;

public class Solution {
    /// <summary>
    /// Distribute minimum candies using two-pass greedy
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public int Candy(int[] ratings) {
        int n = ratings.Length;
        if (n <= 1) return n;

        int[] candies = new int[n];
        Array.Fill(candies, 1);

        // Left-to-right: satisfy left neighbor constraint
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Right-to-left: satisfy right neighbor constraint
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.Max(candies[i], candies[i + 1] + 1);
            }
        }

        return candies.Sum();
    }
}

Approach 3: Single Pass with Slopes

Algorithm:

  1. Traverse the array once, tracking ascending and descending slopes
  2. When going up (ascending slope), increment candy count for each step
  3. When going down (descending slope), track the length of the descent
  4. At the bottom of each descent, calculate candies for the entire descending segment using the formula length * (length + 1) / 2
  5. Adjust the peak if the descending slope is longer than the ascending slope

Time Complexity: O(n) Space Complexity: O(1)

Python:

def candy(ratings):
    """
    Distribute minimum candies using single-pass slope counting
    Time: O(n)
    Space: O(1)
    """
    n = len(ratings)
    if n <= 1:
        return n

    total = 1
    up = 0
    down = 0
    peak = 0

    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            # Ascending
            up += 1
            down = 0
            peak = up
            total += up + 1  # current child gets (up + 1) candies
        elif ratings[i] < ratings[i - 1]:
            # Descending
            up = 0
            down += 1
            # Add candies for descending slope
            total += down
            # If descending slope exceeds the peak, the peak needs one more
            if down > peak:
                total += 1
        else:
            # Equal ratings: reset both slopes
            up = 0
            down = 0
            peak = 0
            total += 1  # current child gets 1 candy

    return total

Java:

class Solution {
    /**
     * Distribute minimum candies using single-pass slope counting
     * Time: O(n)
     * Space: O(1)
     */
    public int candy(int[] ratings) {
        int n = ratings.length;
        if (n <= 1) return n;

        int total = 1;
        int up = 0;
        int down = 0;
        int peak = 0;

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                up++;
                down = 0;
                peak = up;
                total += up + 1;
            } else if (ratings[i] < ratings[i - 1]) {
                up = 0;
                down++;
                total += down;
                if (down > peak) {
                    total++;
                }
            } else {
                up = 0;
                down = 0;
                peak = 0;
                total++;
            }
        }

        return total;
    }
}

Go:

// candy - Distribute minimum candies using single-pass slope counting
// Time: O(n)
// Space: O(1)
func candy(ratings []int) int {
    n := len(ratings)
    if n <= 1 {
        return n
    }

    total := 1
    up := 0
    down := 0
    peak := 0

    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            up++
            down = 0
            peak = up
            total += up + 1
        } else if ratings[i] < ratings[i-1] {
            up = 0
            down++
            total += down
            if down > peak {
                total++
            }
        } else {
            up = 0
            down = 0
            peak = 0
            total++
        }
    }

    return total
}

JavaScript:

/**
 * Distribute minimum candies using single-pass slope counting
 * Time: O(n)
 * Space: O(1)
 */
function candy(ratings) {
    const n = ratings.length;
    if (n <= 1) return n;

    let total = 1;
    let up = 0;
    let down = 0;
    let peak = 0;

    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            up++;
            down = 0;
            peak = up;
            total += up + 1;
        } else if (ratings[i] < ratings[i - 1]) {
            up = 0;
            down++;
            total += down;
            if (down > peak) {
                total++;
            }
        } else {
            up = 0;
            down = 0;
            peak = 0;
            total++;
        }
    }

    return total;
}

C#:

public class Solution {
    /// <summary>
    /// Distribute minimum candies using single-pass slope counting
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int Candy(int[] ratings) {
        int n = ratings.Length;
        if (n <= 1) return n;

        int total = 1;
        int up = 0;
        int down = 0;
        int peak = 0;

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                up++;
                down = 0;
                peak = up;
                total += up + 1;
            } else if (ratings[i] < ratings[i - 1]) {
                up = 0;
                down++;
                total += down;
                if (down > peak) {
                    total++;
                }
            } else {
                up = 0;
                down = 0;
                peak = 0;
                total++;
            }
        }

        return total;
    }
}

Key Insights

  1. Two-Pass Decomposition: The left-to-right pass ensures every child with a higher rating than their left neighbor gets more candies. The right-to-left pass ensures the same for the right neighbor. Taking the maximum at each position satisfies both constraints simultaneously.

  2. Why max() in the Second Pass: Using max(candies[i], candies[i+1] + 1) in the right-to-left pass preserves the constraint established in the first pass. Simply assigning candies[i+1] + 1 could violate the left-neighbor constraint.

  3. Strictly Greater Only: Equal ratings do not require more candies. The child with rating [1,2,2] gets [1,2,1] candies, not [1,2,2].

  4. Slope Counting Insight: The single-pass approach views the ratings as a sequence of ascending and descending slopes. The candy count for a slope of length k is 1 + 2 + ... + k = k*(k+1)/2. The peak between slopes gets the maximum of both slopes’ requirements.

  5. Minimum is Achievable: The two-pass greedy always produces the minimum total because each child gets exactly the minimum candies needed to satisfy both neighbors.

Edge Cases

  • Single child: [5] → 1
  • All equal ratings: [3,3,3,3] → 4 (each child gets 1)
  • Strictly increasing: [1,2,3,4,5] → 15 (candies: 1+2+3+4+5)
  • Strictly decreasing: [5,4,3,2,1] → 15 (candies: 5+4+3+2+1)
  • V-shaped: [3,2,1,2,3] → 9 (candies: 3+2+1+2+3)
  • Mountain: [1,2,3,2,1] → 9 (candies: 1+2+3+2+1)
  • Plateau: [1,2,2,2,1] → 7 (candies: 1+2+1+2+1)
  • Two elements: [1,2] → 3 (candies: 1+2)

Test Cases

# Test case 1: Simple valley
assert candy([1,0,2]) == 5

# Test case 2: Equal neighbors
assert candy([1,2,2]) == 4

# Test case 3: Strictly increasing
assert candy([1,2,3,4,5]) == 15

# Test case 4: Strictly decreasing
assert candy([5,4,3,2,1]) == 15

# Test case 5: Single child
assert candy([5]) == 1

# Test case 6: All equal
assert candy([3,3,3,3]) == 4

# Test case 7: V-shape
assert candy([3,2,1,2,3]) == 9

# Test case 8: Mountain shape
assert candy([1,2,3,2,1]) == 9

# Test case 9: Complex pattern
assert candy([1,3,2,2,1]) == 7

# Test case 10: Two elements, decreasing
assert candy([2,1]) == 3

Common Mistakes

  1. Treating equal ratings as “greater”: The constraint is strictly greater. Children with equal ratings are independent and can each receive 1 candy.

  2. Using assignment instead of max in the second pass: Writing candies[i] = candies[i+1] + 1 instead of candies[i] = max(candies[i], candies[i+1] + 1) breaks the left-neighbor constraint established in the first pass.

  3. Only checking one direction: A single pass (left-to-right only) misses the right-neighbor constraint. For example, [5,4,3,2,1] would incorrectly yield [1,1,1,1,1] with only a left-to-right pass.

  4. Off-by-one in the second pass: The right-to-left pass must iterate from n - 2 down to 0 (inclusive). Starting from n - 1 is harmless but wastes a step.

  5. Forgetting the base case: For a single child, the answer is 1. For an empty array, the answer is 0. Both should be handled explicitly.