[Uber] Minimum candies required to distribute among children with ratings

Problem: 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?

Example:

Input: [2, 1, 0, 2, 3, 1, 6]
Output: 14
Explanation: You can allocate 3, 2, 1, 2, 3, 1, 2 candies respectively.

Approach: Looks like Trapping water problem. We can use the same approach here.

Implementation in C#:

    public int Candy(int[] ratings)

    {

        int length = ratings?.Length ?? 0;

        if (length <= 1)

        {

            return length;

        }

        int[] candies = new int[length];

        Array.Fill(candies, 1);

        for (int i = 1; i < length; ++i)

        {

            if (ratings[i] > ratings[i - 1])

            {

                candies[i] = candies[i - 1] + 1;

            }

        }

        int totalCandies = candies[length - 1];

        for (int i = length - 2; i >= 0; --i)

        {

            if (ratings[i] > ratings[i + 1])

            {

                candies[i] = Math.Max(candies[i], candies[i + 1] + 1);

            }

            totalCandies += candies[i];

        }

        return totalCandies;

    }

Complexity: O(n)