Candy

Difficulty: Hard
Topics: Array, Greedy
Link: https://leetcode.com/problems/candy/

Problem Description

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 get more candies than their neighbors.

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

Example 1:


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

Example 2:


Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104

Solution

1. Problem Deconstruction

Technical Restatement

Given an integer array ratings of length n, assign a positive integer (candy count) to each index such that:

Every index i has at least 1 candy: candies[i] ≥ 1.
For adjacent indices i and i+1:
- If ratings[i] > ratings[i+1], then candies[i] > candies[i+1].
- If ratings[i] < ratings[i+1], then candies[i] < candies[i+1].
- If equal, no constraint beyond the minimum. Minimize the sum of all assigned candies.

Beginner-Friendly Explanation

Imagine a line of children, each with a “rating” number. You must give each child at least one candy. If a child has a higher rating than their immediate neighbor, they must receive more candy than that neighbor. Your goal is to find the smallest total number of candies needed while following these rules.

Mathematical Formulation

Let ( r = [r_0, r_1, …, r_{n-1}] ) be the ratings array. We seek an array ( c = [c_0, c_1, …, c_{n-1}] ) such that:

( c_i \geq 1 \quad \forall i \in [0, n-1] )
For all ( i \in [0, n-2] ):
- ( r_i > r_{i+1} \implies c_i > c_{i+1} )
- ( r_i < r_{i+1} \implies c_i < c_{i+1} ) Minimize ( \sum_{i=0}^{n-1} c_i ).

Constraint Analysis

( n \in [1, 2 \times 10^4] ): Rules out ( O(n^2) ) solutions. Requires ( O(n) ) or ( O(n \log n) ).
Ratings range ( [0, 2 \times 10^4] ): No negative values, but zeros are possible. Equality cases (like [2,2,2]) must be handled.
Hidden Edge Cases:
- All equal ratings: Every child gets 1 candy → total = n.
- Strictly increasing/decreasing: Candy counts must monotonically increase/decrease.
- Alternating peaks/valleys (e.g., [1,3,2,4,1]): Requires careful handling of local minima.

2. Intuition Scaffolding

Analogies

Real-World Metaphor: Like assigning bonuses to employees based on performance scores. Each must get a base bonus, and higher-performing neighbors must get more, but HR wants to minimize total payout.
Gaming Analogy: In a tower defense game, placing towers of varying power along a path. Each tower must have at least one upgrade, and stronger towers must have more upgrades than adjacent weaker ones, while conserving total resources.
Math Analogy: Finding a sequence that satisfies pairwise constraints (like a topological sort in a linear graph with edges for inequalities), then minimizing the sum under linear constraints.

Common Pitfalls

Single-Pass Greedy: Assigning candies left-to-right only fails for sequences like [1,3,2] where right neighbor constraints violate earlier assignments.
Global Min/Max: Starting from the global minimum rating might not work due to multiple local minima.
Equal Ratings Misinterpretation: Assuming equal ratings require equal candies (they don’t; only inequality mandates difference).
Peak Handling: Underestimating candy needs at peaks (e.g., [1,2,3,2,1] requires 9 candies, not 7).
Valley Ignorance: Not recognizing that valleys (local minima) must get 1 candy, forcing neighbors to adjust.

3. Approach Encyclopedia

Brute Force (Naive Recursive)

Idea: For each child, try all possible candy values starting from 1, checking neighbors. Backtrack if constraints fail.

Pseudocode:

def distribute(ratings, candies, idx):
    if idx == len(ratings):
        return sum(candies)
    min_candies = float('inf')
    for c in range(1, len(ratings)+1):
        candies[idx] = c
        if valid(ratings, candies, idx):
            result = distribute(ratings, candies, idx+1)
            min_candies = min(min_candies, result)
    return min_candies

Complexity: ( O(n^n) ) time, ( O(n) ) space. Impractical for ( n \geq 10 ).

Two-Pass Greedy (Optimal)

Idea:
- Left-to-Right Pass: Assign candies ensuring each child has more than their left neighbor if rating is higher.
- Right-to-Left Pass: Adjust to ensure each child has more than their right neighbor if rating is higher.
- Take the maximum of both passes for each child.

Pseudocode:

left = [1] * n
for i in range(1, n):
    if ratings[i] > ratings[i-1]:
        left[i] = left[i-1] + 1

right = [1] * n
for i in range(n-2, -1, -1):
    if ratings[i] > ratings[i+1]:
        right[i] = right[i+1] + 1

total = 0
for i in range(n):
    total += max(left[i], right[i])

Complexity: ( O(n) ) time, ( O(n) ) space.

Visualization:

Ratings:  [1, 3, 2, 4, 1]
Left:     [1, 2, 1, 2, 1]   (only considers left neighbor)
Right:    [1, 2, 1, 3, 1]   (only considers right neighbor)
Final:    [1, 2, 1, 3, 1] → Sum=8

One-Pass Peak-Valley

Idea: Traverse the array, identifying peaks and valleys. Valleys get 1, slopes get increasing counts.
Complexity: ( O(n) ) time, ( O(1) ) space (but tricky to implement).

4. Code Deep Dive

def candy(ratings):
    n = len(ratings)
    left = [1] * n
    # Left pass: handle increasing sequences from left
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            left[i] = left[i-1] + 1
    
    right = [1] * n
    # Right pass: handle decreasing sequences from right
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            right[i] = right[i+1] + 1
    
    total = 0
    for i in range(n):
        # Take the max to satisfy both left and right constraints
        total += max(left[i], right[i])
    return total

Line-by-Line Annotations

left = [1] * n: Initialize all to 1 (minimum candy).
Left loop: If current rating > left neighbor, assign one more than left neighbor.
right = [1] * n: Similarly initialize.
Right loop: If current rating > right neighbor, assign one more than right neighbor.
max(left[i], right[i]): Ensures both constraints are met (e.g., a peak child gets the higher value from both passes).

Edge Case Handling

Example 2 ([1,2,2]):
- Left pass: [1,2,1] (second child gets 2, third gets 1 due to no increase from left).
- Right pass: [1,1,1] → adjusted to [1,2,1] (second child gets 2 from left, third gets 1).
All Equal ([2,2,2]): Both passes yield [1,1,1] → sum=3.

5. Complexity War Room

Hardware-Aware Analysis

For ( n = 2 \times 10^4 ), two arrays left and right use ( 2 \times 20000 \times 4 ) bytes ≈ 160 KB (fits in L2/L3 cache).
Linear passes are cache-friendly.

Comparison Table

Approach	Time Complexity	Space Complexity	Readability	Interview Viability
Brute Force	O(n^n)	O(n)	5/10	❌
Two-Pass Greedy	O(n)	O(n)	9/10	✅ Optimal
One-Pass Peak-Valley	O(n)	O(1)	6/10	⚠️ Complex

6. Pro Mode Extras

Variants

LC 135 (Candy): Standard version (solved above).
LC 123 (Multiple Transactions): Not directly related, but if extended to 2D (e.g., grid of children), use dynamic programming.
Circular Arrangement: If children are in a circle, break into linear segments or use modular arithmetic.

Interview Cheat Sheet

First Mention: “This is a greedy problem with ( O(n) ) time and ( O(n) ) space using two passes.”
Key Insight: “Local minima get 1 candy; slopes increase until peaks.”
Testing: Always test with [1,0,2], [1,2,2], and [1,3,2,4,1].

#135 - Candy