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

# Could be done in O(N) time complexity

**shipra_singh**#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);
```

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

**kripa.iitr**#6

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

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