Coding Interview PatternsCandy
HardGreedy Techniques

Candy

Explanation & Solution

Practice 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 subject to the following requirements:

  • Each child must have at least 1 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 distribute.

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

Output: 5

Explanation: You can allocate [2,1,2] candies to the children respectively. The child at index 1 has the lowest rating so gets 1 candy. Both neighbors have higher ratings and get 2 candies each. Total = 2 + 1 + 2 = 5.

Constraints

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

Approach

Greedy Techniques pattern

1. Initialize the Candies Array

  • Create an array candies of length n, filled with 1 for every child
  • This satisfies the first constraint: each child gets at least 1 candy

2. Left-to-Right Pass

  • Iterate from index 1 to n - 1
  • If ratings[i] > ratings[i - 1], set candies[i] = candies[i - 1] + 1
  • This ensures every child with a higher rating than their left neighbor gets more candies than that neighbor
  • After this pass, all left-neighbor relationships are satisfied

3. Right-to-Left Pass

  • Iterate from index n - 2 down to 0
  • If ratings[i] > ratings[i + 1], set candies[i] = Math.max(candies[i], candies[i + 1] + 1)
  • We take the maximum of the current value and candies[i + 1] + 1 to preserve the constraint already established by the left-to-right pass
  • After this pass, all right-neighbor relationships are also satisfied

4. Sum the Candies

  • Add up all values in the candies array
  • Return the total as the minimum number of candies needed

Key Insight

By splitting the problem into two directional passes, we decouple the left-neighbor and right-neighbor constraints. The left-to-right pass handles increasing sequences from the left, and the right-to-left pass handles increasing sequences from the right. Taking the maximum at each position during the second pass ensures both constraints are satisfied simultaneously. This yields O(n) time complexity and O(n) space complexity.

Solution Code

Previous
Gas Station
Next
Assign Cookies