Problem Explanation:

There are N number of children standing in line. A rating is assigned to each child. The task here is that we have to distribute candies to these children according to the following rules:

1. Each child must get at least one candy.
2. Children with a higher rating get more candies than their neighboring child.

You objective is giving out the minimum amount of candies that you can.

For instance, let's take an example:

Example:

Input: [1,0,2]

• Here, we have 3 children having ratings [1,0,2]
• Since all must be given at least one candy, let's distribute one candy each to all three. [1,1,1]
• Now we have child with rating 0 that has the same amount of candy as the child to its right (with a rating of 2), which is not correct. So, we add one more candy to the third child, making the distribution [1,1,2]
• At this point, we effectively have higher rating child having more candies than its lower rating neighbour

Output: 1+1+2=4

Solution Explanation:

We use a very straightforward greedy approach to solve the problem. This involves going from left to right and then from right to left using two seperate loops.

We initally create two arrays for maintaining the amount of candy, one for moving left to right and the other from moving right to left.

Then we move from left to right, and if a child has higher rating than the the previous, then we update the candy count in the left to right array as one more than previous.

Next step is to move from right to left and update candy count in a similar manner.

Finally, we iterate over the two arrays and for each index choose the maximum candy count from left to right and right to left arrays since we have calculated them independently.

C++ Solution:

1
2c++
3class Solution {
4 public:
5  int candy(vector<int>& ratings) {
6    const int n = ratings.size();
7    int ans = 0;
8    vector<int> l(n, 1);
9    vector<int> r(n, 1);
10
11    // move from left to right
12    for (int i = 1; i < n; ++i)
13      if (ratings[i] > ratings[i - 1])
14        l[i] = l[i - 1] + 1;
15
16    // move from right to left
17    for (int i = n - 2; i >= 0; --i)
18      if (ratings[i] > ratings[i + 1])
19        r[i] = r[i + 1] + 1;
20
21    // choose the maximum candy count from l and r
22    for (int i = 0; i < n; ++i)
23      ans += max(l[i], r[i]);
24
25    return ans;
26  }
27};

Python Solution:

1
2python
3class Solution:
4    def candy(self, ratings: List[int]) -> int:
5        n = len(ratings)
6        l = [1]*n
7        r = [1]*n
8        ans = 0
9
10        # move from left to right
11        for i in range(1, n):
12            if ratings[i] > ratings[i - 1]:
13                l[i] = l[i - 1] + 1
14
15        # move from right to left
16        for i in range(n - 2, -1, -1):
17            if ratings[i] > ratings[i + 1]:
18                r[i] = r[i + 1] + 1
19
20        # choose the maximum candy count from l and r
21        for i in range(n):
22            ans += max(l[i], r[i])
23
24        return ans

Java Solution:

1
2java
3class Solution {
4    public int candy(int[] ratings) {
5        int n = ratings.length;
6        int[] left = new int[n];
7        int[] right = new int[n];
8
9        Arrays.fill(left, 1);
10        Arrays.fill(right, 1);
11
12        for (int i = 1; i < n; i++)
13            if (ratings[i] > ratings[i - 1])
14                left[i] = left[i - 1] + 1;
15
16        for (int i = n - 2; i >= 0; i--)
17            if (ratings[i] > ratings[i + 1])
18                right[i] = right[i + 1] + 1;
19
20        int ans = 0;
21
22        for (int i = 0; i < n; i++) 
23            ans += Math.max(left[i], right[i]);
24
25        return ans;
26    }
27};

JavaScript Solution:

1
2javascript
3var candy = function(ratings) {
4    let n = ratings.length;
5    let left = new Array(n).fill(1);
6    let right = new Array(n).fill(1);
7    let ans = 0;
8
9    for(let i = 1; i < n; i++) {
10        if (ratings[i] > ratings[i - 1]) {
11            left[i] = left[i-1] + 1;
12        }
13    }
14
15    for(let i = n-2; i >= 0; i--) {
16        if (ratings[i] > ratings[i + 1]) {
17            right[i] = right[i+1] + 1;
18        }
19    }
20
21    for(let i = 0; i< n; i++) {
22        ans += Math.max(left[i], right[i]);
23    }
24
25    return ans;
26};

C# Solution:

1
2csharp
3public class Solution {
4    public int Candy(int[] ratings) {
5        int n = ratings.Length;
6        int[] left = new int[n];
7        int[] right = new int[n];
8        int candy = 0;
9        
10        for (int i = 0; i < n; i++) {
11            left[i] = 1;
12            right[i] = 1;
13        }
14        
15        for (int i = 1; i < n; i++) {
16            if (ratings[i] > ratings[i - 1])
17                left[i] = left[i - 1] + 1;
18        }
19        
20        for (int i = n - 2; i >= 0; i--) {
21            if (ratings[i] > ratings[i + 1])
22                right[i] = right[i + 1] + 1;
23        }
24        
25        for (int i = 0; i < n; i++) {
26            candy += Math.Max(left[i], right[i]);
27        }
28        
29        return candy;
30    }
31}

This problem is solved using a greedy approach. The main idea behind the algorithm is that each child should be given at least one candy and children with a higher rating get more candies than their neighboring child.

The algorithm is implemented in Python, Javascript, Java, C++, and C#. It uses two loops, one travelling from left to right and the other one from right to left, ensuring that each child having higher rating than the neighboring child gets more candy.

It is implemented in the following manner:

• Initialize two lists (arrays) left and right both of size equal to the number of children, each being assigned a minimum of 1 candy.
• Iterate left to right on the ratings, if the current child's rating is higher than the previous child then assign one more candy than the previous child to the current child in the left array.
• Similarly, repeat the iteration from right to left applying the same rule and update the right array.
• Now, you have number of candies calculated from both directions independently. Finally, to get the minimum candies, you need to take maximum of the candies calculated from left or right at each child.
• Add all the candies to get the minimum total candies required.

This greedy approach ensures that the minimum total candy is distributed such that the child with higher rating gets more candy than its neighbor.

Although this problem has a very straight forward solution through a greedy approach, it is always recommended to understand and analyze the problem before rushing to the solution.