135. 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 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

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

  1. Candy distribution rules: What are the rules for giving candies? (Assumption: Each child gets at least 1 candy; child with higher rating than neighbor gets more candy)

  2. Neighbor comparison: Which neighbors are compared? (Assumption: Both left and right neighbors - need to satisfy both constraints)

  3. Equal ratings: What happens when two children have the same rating? (Assumption: They can have the same number of candies - no requirement for more)

  4. Optimization goal: What are we optimizing for? (Assumption: Minimize total number of candies while satisfying all constraints)

  5. Minimum requirement: What’s the minimum candies per child? (Assumption: At least 1 candy per child - cannot give 0)

Interview Deduction Process (30 minutes)

Step 1: Brute-Force Approach (8 minutes)

Initial Thought: “I need to assign candies. Let me try all possible assignments that satisfy constraints.”

Naive Solution: Try all possible candy assignments, check if they satisfy constraints (higher rating gets more candy than neighbors), find minimum sum.

Complexity: Exponential time, O(n) space

Issues:

  • Exponential time complexity
  • Too many combinations to try
  • Very inefficient
  • Doesn’t leverage the constraint structure

Step 2: Semi-Optimized Approach (10 minutes)

Insight: “I can use greedy approach: assign minimum candies based on local constraints.”

Improved Solution: Two-pass greedy: first pass left-to-right (if rating[i] > rating[i-1], candy[i] = candy[i-1] + 1), second pass right-to-left (if rating[i] > rating[i+1], candy[i] = max(candy[i], candy[i+1] + 1)).

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

Improvements:

  • O(n) time - much better than exponential
  • Two-pass handles both directions
  • Correctly satisfies all constraints
  • Can be optimized to O(1) space

Step 3: Optimized Solution (12 minutes)

Final Optimization: “I can use single-pass approach with peak/valley detection, or optimize space in two-pass.”

Best Solution: Two-pass greedy is optimal. Can optimize space by using single array and updating in-place. Peak detection approach is alternative but two-pass is clearer.

Complexity: O(n) time, O(n) space (can optimize to O(1) with careful implementation)

Key Realizations:

  1. Two-pass greedy is optimal approach
  2. O(n) time is optimal - must process each child
  3. O(n) space for result array is necessary
  4. Peak/valley detection is alternative approach

Solution Approach

This is a greedy algorithm problem that requires careful handling of increasing and decreasing sequences. The key insight is to track the length of increasing and decreasing sequences and handle the peak case where they meet.

Key Insights:

  1. Increasing Sequence: When ratings increase, give one more candy than the previous child
  2. Equal Ratings: When ratings are equal, reset to 1 candy (no constraint)
  3. Decreasing Sequence: When ratings decrease, track the length of the decreasing sequence
  4. Peak Handling: When a decreasing sequence meets an increasing sequence, ensure the peak child gets enough candies

Algorithm:

  1. Initialize: Start with 1 candy for the first child
  2. Track Sequences: Maintain inc (increasing length) and dec (decreasing length)
  3. Process Each Child:
    • If rating increases: increment candy count
    • If rating is equal: reset to 1
    • If rating decreases: track decreasing sequence length
  4. Handle Peak: When dec == inc, increment dec to ensure peak has enough

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

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

Alternative Approaches

Approach 1: Greedy with Sequence Tracking (Current Solution)

  • Time: O(n)
  • Space: O(1)
  • Best for: Optimal solution, most efficient

Approach 2: Two Passes (Left to Right, Right to Left)

  • Time: O(n)
  • Space: O(n)
  • Use when: Need to store candy array
  • Idea:
    1. Left to right: handle increasing sequences
    2. Right to left: handle decreasing sequences
    3. Take maximum at each position

Approach 3: Peak Detection

  • Time: O(n)
  • Space: O(n)
  • Idea: Find all peaks, then distribute candies from peaks

Edge Cases

  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)

Common Mistakes

  1. Not handling peak: Forgetting to increment dec when dec == inc
  2. Wrong equal handling: Not resetting to 1 when ratings are equal
  3. Wrong sequence tracking: Not properly tracking inc and dec
  4. Off-by-one errors: Incorrect candy calculations
  5. 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