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.

Examples

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.

Example 3:

Input: ratings = [1,3,2,2,1]
Output: 7
Explanation: Ratings: [1,3,2,2,1]
Candies:  [1,2,1,2,1]
Total: 1 + 2 + 1 + 2 + 1 = 7

Constraints

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

Thinking Process

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:

  • Greedy works when local optimal choices lead to global optimum.
  • Often sort first to make the greedy choice obvious.
  • Prove or sanity-check: would swapping two choices ever help?
Greedy choice pick locally best after sorting

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Sort + greedy (this problem) O(n log n) O(1) Interval scheduling, assignment
Local greedy choice O(n) O(1) Jump game, gas station
Greedy + heap O(n log n) O(n) Merge streams, room allocation
Exchange argument O(n) O(1) Prove greedy choice is safe

Solution

Solution: Greedy with Sequence Tracking

class Solution {
public:
    int candy(vector<int>& ratings) {
        const int N = ratings.size();
        int rtn = 1;
        int inc = 1, dec = 0, pre = 1;
        for(int i = 1; i < N; i++) {
            if(ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1: pre + 1;
                rtn += pre;
                inc = pre;
            } else {
                dec++;
                if(dec == inc) {
                    dec++;
                }
                rtn += dec;
                pre = 1;
            }
        }
        return rtn;
    }
};

Solution Explanation

Approach: Sort + greedy (this problem)

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

How the code works:

  • Greedy works when local optimal choices lead to global optimum.
  • Often sort first to make the greedy choice obvious.
  • Prove or sanity-check: would swapping two choices ever help?

Walkthrough — input ratings = [1,0,2], expected output 5:

You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Time: O(n) where n is the number of children · Space: O(1)

Algorithm Explanation:

  1. Initialize (Lines 4-6):
    • rtn: Total candies (starts at 1 for first child)
    • inc: Length of increasing sequence (starts at 1)
    • dec: Length of decreasing sequence (starts at 0)
    • pre: Candies given to previous child (starts at 1)
  2. Process Each Child (Lines 7-19):
    • For each child from index 1 to N-1:
      • If rating increases or equal (ratings[i] >= ratings[i - 1]):
        • Reset decreasing: dec = 0 (we’re in an increasing/equal sequence)
        • Calculate candies:
          • If equal: pre = 1 (no constraint, can give minimum)
          • If increasing: pre = pre + 1 (one more than previous)
        • Add to total: rtn += pre
        • Update increasing length: inc = pre
      • If rating decreases (ratings[i] < ratings[i - 1]):
        • Increment decreasing length: dec++
        • Handle peak: If dec == inc, increment dec again
          • Why: The peak child needs one more candy to satisfy both sides
        • Add to total: rtn += dec
        • Reset previous: pre = 1 (next child after decrease gets minimum)
  3. Return (Line 20):
    • Return total candies

Why This Works:

Key Insight: The algorithm tracks increasing and decreasing sequences separately and handles the peak case where they meet.

Strategy:

  1. Increasing Sequence: Give candies in increasing order (1, 2, 3, …)
  2. Equal Ratings: Reset to 1 (no constraint between equal ratings)
  3. Decreasing Sequence: Give candies in decreasing order (dec, dec-1, …, 1)
  4. Peak Case: When dec == inc, the peak child needs inc + 1 candies to satisfy both increasing and decreasing constraints

Example Walkthrough:

Example 1: ratings = [1,0,2]

Execution:

Initial: rtn = 1, inc = 1, dec = 0, pre = 1

i=1: ratings[1]=0 < ratings[0]=1 (decreasing)
  dec = 1
  dec == inc (1 == 1)? Yes → dec = 2
  rtn = 1 + 2 = 3
  pre = 1
  State: rtn=3, inc=1, dec=2, pre=1

i=2: ratings[2]=2 > ratings[1]=0 (increasing)
  dec = 0
  pre = pre + 1 = 1 + 1 = 2
  rtn = 3 + 2 = 5
  inc = 2
  State: rtn=5, inc=2, dec=0, pre=2

Result: 5
Candies: [2, 1, 2]

Example 2: ratings = [1,2,2]

Execution:

Initial: rtn = 1, inc = 1, dec = 0, pre = 1

i=1: ratings[1]=2 > ratings[0]=1 (increasing)
  dec = 0
  pre = pre + 1 = 1 + 1 = 2
  rtn = 1 + 2 = 3
  inc = 2
  State: rtn=3, inc=2, dec=0, pre=2

i=2: ratings[2]=2 == ratings[1]=2 (equal)
  dec = 0
  pre = 1 (equal, reset to 1)
  rtn = 3 + 1 = 4
  inc = 1
  State: rtn=4, inc=1, dec=0, pre=1

Result: 4
Candies: [1, 2, 1]

Example 3: ratings = [1,3,2,2,1]

Execution:

Initial: rtn = 1, inc = 1, dec = 0, pre = 1

i=1: ratings[1]=3 > ratings[0]=1 (increasing)
  dec = 0
  pre = pre + 1 = 1 + 1 = 2
  rtn = 1 + 2 = 3
  inc = 2
  State: rtn=3, inc=2, dec=0, pre=2

i=2: ratings[2]=2 < ratings[1]=3 (decreasing)
  dec = 1
  dec == inc (1 == 2)? No
  rtn = 3 + 1 = 4
  pre = 1
  State: rtn=4, inc=2, dec=1, pre=1

i=3: ratings[3]=2 == ratings[2]=2 (equal)
  dec = 0
  pre = 1 (equal, reset to 1)
  rtn = 4 + 1 = 5
  inc = 1
  State: rtn=5, inc=1, dec=0, pre=1

i=4: ratings[4]=1 < ratings[3]=2 (decreasing)
  dec = 1
  dec == inc (1 == 1)? Yes → dec = 2
  rtn = 5 + 2 = 7
  pre = 1
  State: rtn=7, inc=1, dec=2, pre=1

Result: 7
Candies: [1, 2, 1, 2, 1]

Algorithm Breakdown

Why Peak Handling is Needed

The Peak Case: When an increasing sequence meets a decreasing sequence, the peak child must satisfy both constraints.

Example: ratings = [1, 3, 2]

  • Child 0: rating 1 → needs at least 1 candy
  • Child 1: rating 3 → needs more than child 0 (increasing) → needs at least 2 candies
  • Child 2: rating 2 → needs less than child 1 (decreasing) → needs at least 1 candy

But wait: If we give child 1 only 2 candies and child 2 gets 1 candy, that’s fine. But if the decreasing sequence is longer…

Example: ratings = [1, 3, 2, 1]

  • If we give: [1, 2, 1, 1]
  • Child 1 has 2, child 2 has 1, child 3 has 1
  • But child 2 (rating 2) should have more than child 3 (rating 1)
  • So we need: [1, 3, 2, 1]

The Fix: When dec == inc, we increment dec to ensure the peak child gets enough candies.

Why Equal Ratings Reset to 1

Equal Ratings: When two children have the same rating, there’s no constraint between them.

Example: ratings = [2, 2, 1]

  • Child 0: rating 2 → 1 candy
  • Child 1: rating 2 → 1 candy (no constraint with child 0)
  • Child 2: rating 1 → 1 candy (less than child 1, but child 1 only has 1, so child 2 also gets 1)

Result: [1, 1, 1] is valid.

Sequence Tracking

Increasing Sequence (inc):

  • Tracks the length/candies of the increasing sequence
  • Used to determine if peak needs adjustment

Decreasing Sequence (dec):

  • Tracks the length of the decreasing sequence
  • When dec == inc, the peak needs one more candy

Time & Space Complexity

  • Time Complexity: O(n) where n is the number of children
    • Single pass through the ratings array
    • Each iteration does O(1) work
  • Space Complexity: O(1)
    • Only using a few variables (rtn, inc, dec, pre)
    • No additional data structures

Key Points

  1. Greedy Choice: Process children left to right, making locally optimal choices
  2. Sequence Tracking: Track increasing and decreasing sequence lengths
  3. Peak Handling: When dec == inc, increment dec to handle peak case
  4. Equal Ratings: Reset to 1 candy when ratings are equal
  5. Optimal: This greedy strategy finds the minimum candies needed

Common Mistakes

  1. Single child: [1] → return 1
  2. All equal: [1,1,1] → return 3 (each gets 1)
  3. Strictly increasing: [1,2,3,4] → return 10 (1+2+3+4)
  4. Strictly decreasing: [4,3,2,1] → return 10 (4+3+2+1)

  5. Peak in middle: [1,3,2] → return 5 (1+2+2)

  6. Not handling peak: Forgetting to increment dec when dec == inc
  7. Wrong equal handling: Not resetting to 1 when ratings are equal
  8. Wrong sequence tracking: Not properly tracking inc and dec
  9. Off-by-one errors: Incorrect candy calculations
  10. Not understanding constraints: Confusing “more candies” with “at least one more”

Follow-Up: Why dec == inc Needs Adjustment

Question: Why do we increment dec when dec == inc?

Answer:

  • When dec == inc, the decreasing sequence length equals the increasing sequence length
  • The peak child needs to satisfy both: more than the previous (increasing) and more than the next (decreasing)
  • If we give the peak inc candies and the next child dec candies, but dec == inc, the peak only has inc candies
  • However, the peak needs at least inc + 1 candies to be more than both neighbors
  • By incrementing dec, we effectively give the peak one more candy

Example: ratings = [1, 3, 2, 1]

  • Without adjustment: [1, 2, 1, 1] → peak has 2, but next has 1 (should be fine, but…)
  • Actually, if dec=1 and inc=2, peak gets 2, next gets 1, that’s fine
  • But if dec=2 and inc=2, peak gets 2, but we need peak to have 3 to satisfy both sides
  • So we increment dec to 3, giving peak effectively 3 candies

Tags

Array, Greedy, Hard

Key Takeaways

  • Greedy works when local optimal choices lead to global optimum.
  • Often sort first to make the greedy choice obvious.
  • Prove or sanity-check: would swapping two choices ever help?

References

Template Reference