Candy - LeetCode Solution in C++, Java, Python

1. Introduction

The "Candy" problem requires allocating candies to children standing in a line, such that each child gets at least one candy, and children with higher ratings than their neighbors receive more candies. The goal is to determine the minimum total number of candies required.

2. Problem

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

- Each child must have at least one candy.

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

Return the minimum number of candies you need to have to distribute the candies to the children.

3. Solution in C++

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> candies(n, 1);

    // Left to right
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1])
            candies[i] = candies[i - 1] + 1;
    }

    // Right to left
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1])
            candies[i] = max(candies[i], candies[i + 1] + 1);
    }

    return accumulate(candies.begin(), candies.end(), 0);
}

Explanation:

1. Initialize a vector candies to store the number of candies for each child, initially 1 for all.

2. First, iterate from left to right, increasing the candy count for a child if their rating is higher than the left neighbor.

3. Then, iterate from right to left, doing the same check with the right neighbor, ensuring the current child gets more candies if necessary.

4. Sum up the candies in the candies vector to get the minimum total number of candies required.

4. Solution in Java

public int candy(int[] ratings) {
    int n = ratings.length;
    int[] candies = new int[n];
    Arrays.fill(candies, 1);

    // Left to right
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1])
            candies[i] = candies[i - 1] + 1;
    }

    // Right to left
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1])
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }

    int total = 0;
    for (int candy : candies)
        total += candy;
    return total;
}

Explanation:

1. Create an array candies and initialize it with 1 for each child.

2. Traverse the ratings array from left to right, increasing the number of candies for a child if they have a higher rating than the left neighbor.

3. Then, traverse from right to left, adjusting the candy count to satisfy the condition with the right neighbor.

4. Sum up the values in the candies array to find the minimum total number of candies needed.

5. Solution in Python

def candy(ratings):
    n = len(ratings)
    candies = [1] * n

    # Left to right
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    # Right to left
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)

    return sum(candies)

Explanation:

1. Initialize a list candies with 1 candy for each child.

2. Iterate through ratings from left to right, increasing the candy count if a child has a higher rating than the left neighbor.

3. Iterate from right to left, ensuring children with a higher rating than their right neighbor have more candies.

4. The sum of the candies list gives the minimum number of candies required.