Candy - Leetcode Solution

The Candy problem on LeetCode is a programming challenge that requires you to distribute candies to children in such a way that every child gets at least one candy, and the total number of candies you distribute is minimal. Here's a detailed solution that solves this problem using the greedy approach.

Algorithm:

1. First, create an array called "candies" of size n for n children.

2. Set all element values of the candies array to 1, so that each child gets at least one candy.

3. Traverse the array from left to right and compare each child's ratings with the previous child's rating.

4. If the current child's rating is greater than the previous child's rating, then you add 1 to the candies[i] value (i.e., increase the number of candies to the current child).

5. Traverse the array again from right to left and compare each child's rating with the next child's rating.

6. If the current child's rating is greater than the next child's rating and the candies[i] value is less than or equal to candies[i+1] (where i is the current position), then you add 1 to the candies[i] value (i.e., increase the number of candies to the current child).

7. Return the sum of all candies values in the candies array.

Python Code:

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

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

for i in range(n-2, -1, -1):
    if ratings[i] > ratings[i+1] and candies[i] <= candies[i+1]:
        candies[i] = candies[i+1] + 1

return sum(candies)

Test Cases:

Let's test the function with some input data.

Test Case 1:

ratings = [1,0,2] => output = 5 assert(candy(ratings) == 5)

Explanation: The optimal distribution should be [2, 1, 2] (where each number represents the number of candies each child gets). Child 1 gets 2 candies because his/her rating is higher than child 2, child 2 gets 1 candy, and child 3 gets 2 candies because his/her rating is higher than child 2.

Test Case 2:

ratings = [1,2,2] => output = 4 assert(candy(ratings) == 4)

Explanation: The optimal distribution should be [1, 2, 1] (where each number represents the number of candies each child gets). Child 1 gets 1 candy, child 2 gets 2 candies, and child 3 gets 1 candy.

Test Case 3:

ratings = [1,3,4,5,2] => output = 11 assert(candy(ratings) == 11)

Explanation: The optimal distribution should be [1, 2, 3, 4, 1] (where each number represents the number of candies each child gets). Child 1 gets 1 candy, child 2 gets 2 candies, child 3 gets 3 candies, child 4 gets 4 candies, and child 5 gets 1 candy.

1