Problem Statment

You are given ratings array of integers where ratings[i] is rating value assigned to the i^th child. You are giving candies to these n children who are standing in single row.

Follow below rules to give candies to each child:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum count of candies you require to distribute candies to the children.

Examples

• Example 1:

  • Input: ratings = [4, 2, 3, 4]
  • Expected Output: 8
  • Justification: The second child gets 1 candy (lowest rating), the third gets 2 candies (higher than the second), the first gets 2 (higher than the second but equal to the third), and the fourth gets 3 (highest rating).

• Example 2:

  • Input: ratings = [1, 1, 1]
  • Expected Output: 3
  • Justification: All children have the same rating, so each gets 1 candy to satisfy the minimum requirement.

• Example 3:

  • Input: ratings = [2, 4, 2, 6, 1, 7, 8]
  • Expected Output: 12
  • Justification: We can give candies to each child as given in [1, 2, 1, 2, 1, 2, 3], totaling 12 candies.

Solution

To solve this problem, we'll use a two-pass strategy to ensure fairness and efficiency. Initially, we assign one candy to every child to meet the base requirement. Then, we traverse the ratings from left to right, increasing the candy count for a child if their rating is higher than the previous child's, ensuring they receive more candies than the child before them. This guarantees that the "higher rating, more candies" rule is upheld in one direction.

However, this is not enough, as we must also check this condition in the reverse direction. To do this, we then traverse the ratings from right to left, adjusting the candy counts similarly but only increasing a child's candy if doing so would not decrease the candy count already assigned from the left-to-right pass.

This method ensures all conditions are met with the minimal amount of candy distributed, taking into account the requirements from both neighboring sides.

Step-by-Step Algorithm

1. Initialize an Array:

   • Create an array candies with the same length as the ratings array, and fill it with 1. This ensures every child receives at least one candy initially.

2. First Pass (Left to Right):

   • Start from the first child (index 0) and iterate through the ratings array to the last child.
   • For each child, compare their rating with the previous child's rating.
   • If the current child's rating is higher than the previous child's, increase the current child's candies by giving them one more candy than the previous child. This is done by setting candies[i] = candies[i-1] + 1.

3. Second Pass (Right to Left):

   • Start from the last child (second-to-last index) and iterate through the ratings array towards the first child.
   • For each child, compare their rating with the next child's rating (the child on their right).
   • If the current child's rating is higher than the next child's and they do not already have more candies, adjust their candies. Specifically, give the current child one more candy than the next child if necessary, ensuring that candies[i] = candies[i+1] + 1.

4. Calculate Total Candies:

   • Sum up all the values in the candies array. This total represents the minimum number of candies needed to satisfy the conditions.

Algorithm Walkthrough

Let's consider the Input: ratings = [2, 4, 2, 6, 1, 7, 8]

1. Initialization:

   • ratings = [2, 4, 2, 6, 1, 7, 8]
   • candies = [1, 1, 1, 1, 1, 1, 1] (Each child gets at least one candy)

2. First Pass (Left to Right):

   • Compare 4 to 2: Increase candies for the second child, candies = [1, 2, 1, 1, 1, 1, 1]
   • Compare 2 to 4: No increase, as 2 is not greater than 4.
   • Compare 6 to 2: Increase candies for the fourth child, candies = [1, 2, 1, 2, 1, 1, 1]
   • Compare 1 to 6: No increase, as 1 is not greater than 6.
   • Compare 7 to 1: Increase candies for the sixth child, candies = [1, 2, 1, 2, 1, 2, 1]
   • Compare 8 to 7: Increase candies for the seventh child, candies = [1, 2, 1, 2, 1, 2, 3]

3. Second Pass (Right to Left):

   • Compare 7 to 8: No increase needed, as we're adjusting for higher ratings to the right.
   • Compare 1 to 7: No increase needed, as we're adjusting for higher ratings to the right.
   • Compare 6 to 1: No increase needed, as candies[3] > candies[4].
   • Compare 2 to 6: No increase, as we're adjusting for higher ratings to the right.
   • Compare 4 to 2: No increase needed, as the second child already has more than the third.
   • Compare 2 to 4: No increase needed, as we're adjusting for higher ratings to the right.

4. Calculate Total Candies:

   • Summing the candies array gives us 1 + 2 + 1 + 2 + 1 + 2 + 3 = 12 candies needed in total.

Code

Complexity Analysis

Time Complexity

• O(n): The algorithm involves iterating over the ratings array twice—once from left to right and once from right to left. Since each pass is linear with respect to the length of the ratings array, the overall time complexity is linear, O(n), where n is the number of children (or the length of the ratings array).

Space Complexity

• O(n): Additional space is required for the candies array, which stores the number of candies for each child. This array is the same length as the ratings array, so the space complexity is O(n).