There are *N* children standing in a line. Each child is assigned a rating value.

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.

What is the minimum candies you must give?

**Solution 1**: The trick part is equal rating. When we find the next child with the same rate as previous child, do we give them 1 candy or more? we do not know until we know how many children following with rating less then he. so we can use array to keep how many candy child has and forward and backward iterative.

public int Candy(int[] ratings) { var candies = new int[ratings.Length]; // from left to right for (int i = 0; i < ratings.Length; i++) { if (i > 0 && ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] + 1; } else { candies[i] = 1; } } // from right to left for (int i = ratings.Length - 1; i >= 0; i--) { if (i < ratings.Length - 1 && ratings[i] > ratings[i + 1]) { candies[i] = Math.Max(candies[i + 1] + 1, candies[i]); } } return candies.Sum(); }

**Solution 2**: Let us give a candy to the first child. Then for each child we have three cases:

- His/her rating is equal to the previous one -> give 1 candy.
- His/her rating is greater than the previous one -> give him (previous + 1) candies.
- His/her rating is less than the previous one -> don’t know what to do yet, let’s just count the number of such consequent cases.

If we think the problem like this way, then equal rating issue is solved. Number of candy equal rating children got is totally depends on how many children with rating continues to less than previous’.

public int Candy(int[] ratings) { var numberOfCandy = 1; var previousCandyCount = 1; var lessCount = 0; for (int i = 1; i < ratings.Length; i++) { if (ratings[i] >= ratings[i - 1]) { if (lessCount > 0) { numberOfCandy += (lessCount*(lessCount + 1))/2; if (lessCount >= previousCandyCount) { numberOfCandy += lessCount - previousCandyCount + 1; } previousCandyCount = 1; lessCount = 0; } previousCandyCount = ratings[i] == ratings[i - 1] ? 1 : previousCandyCount + 1; numberOfCandy += previousCandyCount; } else { lessCount++; } } if (lessCount > 0) { numberOfCandy += (lessCount * (lessCount + 1)) / 2; if (lessCount >= previousCandyCount) { numberOfCandy += lessCount - previousCandyCount + 1; } } return numberOfCandy; }