Distribute Candy

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:

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

What is the minimum candies you must give?

Input Format:

The first and the only argument contains N integers in an array A.

Output Format:

Return an integer, representing the minimum candies to be given.

Example:

Input 1:
    A = [1, 2]

Output 1:
    3

Explanation 1:
    The candidate with 1 rating gets 1 candy and candidate with rating cannot get 1 candy as 1 is its neighbor. 
    So rating 2 candidate gets 2 candies. In total, 2 + 1 = 3 candies need to be given out.

Input 2:
    A = [1, 5, 2, 1]

Output 2:
    7

Explanation 2:
    Candies given = [1, 3, 2, 1]
Method1:

Suppose the array is [-1, -2, -3, 4, 5], the candy distribution should be [-1(3), -2(2), -3(1), 4(2), 5(3)], the total number of candies being 11.

Since each person should have a minimum candy 1, you assign 1 to every person initially. Now,
in the first pass you move from left to right and increment the number of candies whenever A[i] > A[i-1]. Since, a change in count_of_candies[A[i]] will also affect count_of_candies[A[i+1]], we propagate right, modifying the count array.

Similarly, in the second pass, we move from right to left to consider the cases where A[i] > A[i+1], and increment the count_of_candies[A[i]]. A change in count_of_candies[A[i]] can also affect count_of_candies[A[i-1]] so we propagate left, modifying the count array.

Solution1:

Time: O(n)
Space: O(n)

public class Solution {
    public int candy(ArrayList<Integer> A) {
        int[] candies = new int[A.size()];
        for (int i = 0; i < candies.length; i ++) {
            candies[i] = 1;
        }
        for (int i = 1; i < A.size(); i ++) {
            if (A.get(i) > A.get(i - 1)) {
                candies[i] = Math.max(candies[i], candies[i - 1] + 1);
            }
        }
        for (int i = A.size() - 2; i >= 0; i --) {
            if (A.get(i) > A.get(i + 1)) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }
        int sum = 0;
        for (int i : candies) {
            sum += i;
        }
        return sum;
    }
}

Solution2:

int Solution::candy(vector<int> &rates) {
    int result = 0;
    
    int candles = 0;
    int previousRate = INT_MIN;
    int lastTopPosition = 0;
    int lastTopCandles = 0;
    
    for(int i = 0; i < rates.size(); i++){
        
        int currentRate = rates[i];
        int currentIncrement = INT_MIN;
        
        if(currentRate >= previousRate){
            
            candles = currentRate == previousRate ? 1 : candles + 1;
            currentIncrement = candles;
            
            lastTopPosition = i;
            lastTopCandles = candles;
        }
        else {
            
            currentIncrement  = i - lastTopPosition;
            
            if(lastTopCandles <= currentIncrement){
                lastTopCandles++;
                currentIncrement++;
            }
            
            candles = 1;
        }
        
        result += currentIncrement;
        previousRate = currentRate;
    }
    
    return result;
}