Intuition

My thought was first going left to right checking both neighbours. For example, for [1,2,3,4] would work perfectly.

However it’s not possible to solve this in one pass checking both neighbours. We need to use a two pass approach, LTR, RTL.

To visualize better the problem, using [1,2,3,4] let’s see how many candies LTR and RTL would give for each children:

LTR
[1,2,3,4] -> [1,2,3,4]
since it's always increase each children get's one more candy than the previous one.

RTL
[1,2,3,4] -> [1,1,1,1]
From RTL perspective, it's always decreasing, so all children get's one.

In this case the correct solution is [1,2,3,4]

Now, let’s see this other example [3,2,1,2,3]

LTR
[3,2,1,2,3] -> [1,1,1,2,3]

RTL
[3,2,1,2,3] -> [3,2,1,1,1]

The solution here the the max between the two arrays.

Approach

Initilize two arrays, L and R with one element. From left to right check if the current element is greater than the previous one, if it is, this child has previous+1 candies.

We do the same right to left (reversed loop), check if the current element if greater than the next one, if it is, this child has next+1 candies.

The answer is the max of each arrays’ element.

Complexity

• Time complexity: O(n)
  • linear time, 3 passes (ltr, rtl, answer)
• Space complexity: O(n)
  • two control arrays

Code

class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """

        L = [1] * len(ratings)
        R = [1] * len(ratings)

        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                L[i] = L[i-1] + 1

        for i in reversed(range(0, len(ratings)-1)):
            if ratings[i] > ratings[i+1]:
                R[i] = R[i+1] + 1

        return sum(max(R[i],L[i]) for i in range(len(L)))