Array Sorting Greedy
Proficient Level

Implement the candyDistributionMinimum method that returns the minimum candies needed while respecting rating rules.

The input array ratings contains the rating of each child standing in a line.

Your task is to return the minimum number of candies needed so that every child gets at least one candy, and any child with a higher rating than an immediate neighbour gets more candies than that neighbour.

For example, for [1,0,2], the minimum candies distribution can be [2,1,2], so the answer is 5.

Example 1
Input:
ratings (int[]) = [1,0,2]
size (int) = 3
Return:
(int) 5
Example 2
Input:
ratings (int[]) = [1,2,2]
size (int) = 3
Return:
(int) 4
Example 3
Input:
ratings (int[]) = [1,3,4,5,2]
size (int) = 5
Return:
(int) 11

Use two passes because each child has a left neighbour and a right neighbour.

Start by giving every child one candy. In the left-to-right pass, if a child has a higher rating than the child on the left, give one more candy than the left child. In the right-to-left pass, if a child has a higher rating than the child on the right, make sure the child has more candies than the right child.

The sum of the final candy array is the minimum required candies.

Pseudocode:

function candyDistributionMinimum(ratings, size):
    candies = array of size filled with 1
    for i from 1 to size - 1:
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1
    for i from size - 2 down to 0:
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)
    total = 0
    for each candy in candies:
        total = total + candy
    return total
Run your code to see the result.