I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) solutions.
Now, I was thinking about the generalized problem which consider k neighbors(i.e. for the ith child we have to consider children from max(1, i-k)th place to min(n, i+k)th place) rather considering only one neighbour.
So, the problem is basically for every i in range[1, n] distribute candies in the children from max(1, i-k) to min(n, i+k) in such a way that each one gets at least one candy and if there are p children who have higher rating than ith child inside the window, then they will get more candies than the ith child.
Is there any linear time solution for this?