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;
}