Candy Solution for Accenture

Company: Accenture · Difficulty: Hard · Topics: Array, Greedy, Dynamic Programming

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:

1. Each child must have at least one candy.

2. Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you must give to the children.

Key Understanding:

• Each child must receive at least 1 candy
• If a child has a higher rating than their neighbor, they must get more candies
• We need to satisfy both left and right neighbor constraints
• The goal is to minimize the total number of candies distributed

Examples

Example 1:

Input: ratings = [1,0,2]

Output: 5

Explanation:

• Child 0 (rating 1): gets 2 candies (higher than child 1)
• Child 1 (rating 0): gets 1 candy (minimum)
• Child 2 (rating 2): gets 2 candies (higher than child 1)
• Total: 2 + 1 + 2 = 5 candies
• Visual: [1,0,2] → [2,1,2] candies

Example 2:

Input: ratings = [1,2,2]

Output: 4

Explanation:

• Child 0 (rating 1): gets 1 candy (minimum)
• Child 1 (rating 2): gets 2 candies (higher than child 0)
• Child 2 (rating 2): gets 1 candy (same rating as child 1, but no right neighbor)
• Total: 1 + 2 + 1 = 4 candies
• Visual: [1,2,2] → [1,2,1] candies

Example 3:

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

Output: 7

Explanation:

• Child 0 (rating 1): gets 1 candy
• Child 1 (rating 3): gets 3 candies (higher than both neighbors)
• Child 2 (rating 2): gets 2 candies (higher than child 3)
• Child 3 (rating 2): gets 1 candy (same as child 2, but no right neighbor)
• Child 4 (rating 1): gets 1 candy
• Total: 1 + 3 + 2 + 1 + 1 = 8 candies

Intuition

The key insight is that we need to consider both left-to-right and right-to-left relationships. A child's candy count depends on both their left and right neighbors.

Two-Pass Approach:

1. Left to Right Pass: Ensure each child gets more candies than their left neighbor if they have a higher rating

2. Right to Left Pass: Ensure each child gets more candies than their right neighbor if they have a higher rating

3. Take Maximum: For each child, take the maximum of the two passes to satisfy both constraints

Why This Works:

• The left-to-right pass handles increasing sequences
• The right-to-left pass handles decreasing sequences
• Taking the maximum ensures both neighbor constraints are satisfied
• This guarantees the minimum total candies while satisfying all requirements

Approach

Approach 1: Two-Pass Greedy (Optimal)

Algorithm:

1. Initialize all children with 1 candy

2. Left to right pass: if rating[i] > rating[i-1], then candy[i] = candy[i-1] + 1

3. Right to left pass: if rating[i] > rating[i+1], then candy[i] = max(candy[i], candy[i+1] + 1)

4. Sum all candies and return

Key Steps:

• First pass ensures left neighbor constraint
• Second pass ensures right neighbor constraint
• Taking maximum ensures both constraints are satisfied

Approach 2: Peak-Valley Analysis

Algorithm:

1. Find all peaks (local maxima) in the ratings

2. For each peak, calculate candies needed for the increasing and decreasing sequences

3. Sum all candies

Complexity:

• Time: O(n)
• Space: O(1)
• More complex to implement

Approach 3: Dynamic Programming

Algorithm:

1. Use DP array to store minimum candies for each position

2. For each position, consider both left and right dependencies

3. Use memoization to avoid recalculations

Complexity:

• Time: O(n)
• Space: O(n)
• More complex than two-pass approach

Dry Run

Example: ratings = [1,0,2]

Step 1: Initialize all with 1 candy

• candies = [1,1,1]

Step 2: Left to right pass

• i=0: no left neighbor, keep 1
• i=1: rating[1] < rating[0], keep 1
• i=2: rating[2] > rating[1], set candies[2] = candies[1] + 1 = 2
• candies = [1,1,2]

Step 3: Right to left pass

• i=2: no right neighbor, keep 2
• i=1: rating[1] < rating[2], keep 1
• i=0: rating[0] > rating[1], set candies[0] = max(1, candies[1] + 1) = max(1, 2) = 2
• candies = [2,1,2]

Step 4: Calculate total

• Total = 2 + 1 + 2 = 5

Key Insights

1. Two-Pass Necessity: A single pass is insufficient because a child's candy count depends on both neighbors

2. Greedy Nature: At each step, we give the minimum candies needed to satisfy the current constraint

3. Peak Handling: Peaks (local maxima) require the most candies

4. Plateau Handling: Children with same ratings can have different candy counts based on their neighbors

5. Boundary Conditions: First and last children only have one neighbor to consider

Edge Cases

1. Single Child: Only one child, gets 1 candy

2. All Same Ratings: All children get 1 candy

3. Strictly Increasing: Each child gets one more candy than the previous

4. Strictly Decreasing: Each child gets one more candy than the next

5. Peaks and Valleys: Complex patterns with multiple peaks

6. Large Arrays: Handle arrays with thousands of children efficiently

Time & Space Complexity

Approach 1 (Two-Pass Greedy):

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

Approach 2 (Peak-Valley):

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

Approach 3 (Dynamic Programming):

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

More Accenture coding questions