Candy

Candy

What is this problem about?

The Candy interview question is a classic greedy optimization problem. You are given an array of ratings for n children standing in a line. You need to distribute candies such that:

1. Each child must have at least one candy.
2. Children with a higher rating than their neighbors get more candies than their neighbors. The goal is to find the minimum total number of candies you need to satisfy these conditions. This Candy coding problem is a test of local vs. global optimization.

Why is this asked in interviews?

Tech giants like Google, Amazon, and Microsoft frequently use this question to evaluate a candidate's ability to handle dependencies in data. It requires realizing that a child's candy count depends on both their left and right neighbors. It tests whether you can break a two-way dependency into two one-way passes, which is a common technique for optimizing array problems.

Algorithmic pattern used

This utilizes the Array, Greedy interview pattern, specifically a Two-Pass approach.

1. Left-to-Right Pass: Ensure each child has more candies than their left neighbor if their rating is higher.
2. Right-to-Left Pass: Ensure each child has more candies than their right neighbor if their rating is higher, while maintaining the condition from the first pass. The final candy count for each child is the maximum of the results from both passes.

Example explanation

Ratings: [1, 0, 2]

1. Initialize candies: [1, 1, 1]
2. Left-to-Right:
   • Index 1 (0) < Index 0 (1): No change.
   • Index 2 (2) > Index 1 (0): Candies[2] = candies[1] + 1 = 2.
   • State: [1, 1, 2]
3. Right-to-Left:
   • Index 1 (0) < Index 2 (2): No change.
   • Index 0 (1) > Index 1 (0): Candies[0] = candies[1] + 1 = 2.
   • State: [2, 1, 2] Total: 2 + 1 + 2 = 5.

Common mistakes candidates make

• One-Pass attempt: Trying to solve it in a single pass, which often misses dependencies (e.g., a long decreasing sequence).
• Misinterpreting "More": Thinking a child with the same rating as their neighbor must have the same number of candies. The rule only applies to higher ratings.
• Initialization: Forgetting to start every child with at least 1 candy.

Interview preparation tip

Whenever a value depends on neighbors on both sides, consider a two-pass approach (one forward, one backward). It simplifies the logic and usually results in an O(N) time and O(N) space solution.