Solution: Candy

Let’s solve the Candy problem using the Greedy Techniques pattern.

We'll cover the following

Statement

You are given an array ratings where ratings[i] represents the rating of the i-th child standing in a line. Your task is to distribute candies to each child based on the following rules:

  1. Every child must receive at least one candy.

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

Determine the minimum total number of candies you must distribute to satisfy the above conditions.

Constraints:

  • 1≤1 \leq ratings.length ≤1000\leq 1000

  • 0≤0 \leq ratings[i] ≤1000\leq 1000

Solution

We use a greedy strategy with two passes through the ratings array to distribute candies while ensuring that each child gets at least one candy and that children with higher ratings than their neighbors receive more candies. In the first pass (left to right), we check if a child has a higher rating than the previous one—if so, they receive one more candy than the previous child. This handles increasing sequences from the left. In the second pass (right to left), we check if a child has a higher rating than the next one—if so, we update their candy count to be the maximum of their current candy count and one more than the next child’s. This second pass corrects any violations introduced in the first pass, particularly for decreasing rating sequences. This two-pass greedy approach guarantees the minimum number of candies needed by ensuring each child gets at least one candy and adjusting based on both neighbors.

The steps of the algorithm are as follows:

  1. Initialize a candies array where each child is assigned one candy.

  2. Traverse from left to right:

    1. For each child i from 1 to n - 1:

      1. If ratings[i] > ratings[i - 1], set candies[i] = candies[i - 1] + 1.

  3. Traverse from right to left:

    1. For each child i from n - 2 to 0:

      1. If ratings[i] > ratings[i + 1], set candies[i] = max(candies[i], candies[i + 1] + 1).

  4. Return the total number of candies by summing all elements in the candies array.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.