Could be done in O(N) time complexity


#1

Run two passes: one from left to right and another from right to left


#2

Can you explain why 2 passes will be required?


#3

It could be done in linear complexity using recursion.


#4

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.

    for(int i = 1; i < A.size(); i++)
        if(A[i] > A[i-1])
          count[i] = max(count[i], count[i-1] + 1);
    
    for(int i = A.size()-2; i >= 0; i--)
        if(A[i] > A[i+1])
          count[i] = max(count[i], count[i+1] + 1);

#5

int Solution::candy(vector &A) {
int count[10000],sum;
for (int i=0;i<A.size();i++){
count[i]=1;
}
for(int i = 1; i < A.size(); i++)
if(A[i] > A[i-1])
count[i] = max(count[i], count[i-1] + 1);

for(int i = A.size()-2; i >= 0; i--)
    if(A[i] > A[i+1])
      count[i] = max(count[i], count[i+1] + 1);
  for (int i=0;i<A.size();i++){
    sum=sum+count[i];
}    

return (sum);
} // I tried implementing this method , but i am getting segmentation fault


#6

@asmitha-satesh define count array of size A.size() instead of 10000. it will give correct answer.


#7

https://leetcode.com/problems/candy/solution/ check out this link for explaination