Candy

Problem Statement

In this problem, we are given a line of n children, each assigned a specific rating which is represented by an integer array called ratings. The task involves distributing candies such that:

• Every child receives at least one candy.
• A child with a higher rating than his/her adjacent neighbors receives more candies compared to those neighbors.

The goal is to determine the minimum number of candies required to meet these distribution rules.

Examples

Example 1

Input:

ratings = [1,0,2]

Output:

5

Explanation:

You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2

Input:

ratings = [1,2,2]

Output:

4

Explanation:

You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints

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

Approach and Intuition

To solve this problem efficiently while ensuring all given conditions are met, we can approach it using two passes through the ratings array:

1. First Pass (Left to Right): Start by allocating each child one candy. Then, iterate from the beginning to the end of the ratings array. If a child has a higher rating than the preceding child, give him/her one more candy than the preceding child.

2. Second Pass (Right to Left): After the first pass, sometimes the left neighbor might have a higher rating, but fewer candies than the right neighbor due to adjustments made for other children. To rectify this, make another pass through the list from the end to the beginning. If a child has a higher rating than the next child but has equal or fewer candies, then increase their candy count to one more than the child with the next rating.

This approach ensures that each child gets more candies than their lower-rated neighbors after adjustments from both directions, meeting the conditions. Count the total candies distributed to find the minimum number required. Here's how it appears with the given examples:

• Example 1 demonstrates allocating 2, 1, 2 candies which ensures the child with rating 0 (second child) gets fewer candies than its neighbors.
• Example 2 demonstrates allocating 1, 2, 1 candy where even with the last two children having the same rating, they receive the same count of candies.

Through these steps, while traversing the list twice, we can efficiently calculate the exact number of candies required.

Solutions

class Solution {
public:
    int sumOfNaturalNumbers(int n) { return (n * (n + 1)) / 2; }
    int distributeCandies(vector<int>& ratings) {
        if (ratings.size() <= 1) {
            return ratings.size();
        }
        int totalCandies = 0;
        int ascending = 0;
        int descending = 0;
        int previousSlope = 0;
        for (int i = 1; i < ratings.size(); i++) {
            int currentSlope = (ratings[i] > ratings[i - 1])
                               ? 1
                               : (ratings[i] < ratings[i - 1] ? -1 : 0);
                
            if ((previousSlope > 0 && currentSlope == 0) || (previousSlope < 0 && currentSlope >= 0)) {
                totalCandies += sumOfNaturalNumbers(ascending) + sumOfNaturalNumbers(descending) + max(ascending, descending);
                ascending = 0;
                descending = 0;
            }
                
            if (currentSlope > 0) {
                ascending++;
            } else if (currentSlope < 0) {
                descending++;
            } else {
                totalCandies++;
            }
            previousSlope = currentSlope;
        }
        totalCandies += sumOfNaturalNumbers(ascending) + sumOfNaturalNumbers(descending) + max(ascending, descending) + 1;
        return totalCandies;
    }
};