LeetCode 135. Candy

This is a hard question that has many different solutions. In this article, I’ll discuss two of them. The first one is more intuitive and the second one is more succinct, but harder to come up with.

The question is as follows: We have n children standing in a line. Each child is assigned a rating value given in the integer array ratings. The task is to give candies to the children with the following requirements:

1. Each child must have at least one candy.
2. Children with a higher rating get more candies than their neighbours.

Return the minimum number of candies you need to have to distribute the candies to the children.

As a first thought, one might use a greedy algorithm: first find the lowest rating in the array, assign one candy to that child and and then go left and right, incrementing or decrementing the amount of candies depending on the ratings.

However, this algorithm has one caveat: children that have lower ratings might get more candies than necessary. Consider this array of ratings: [3, 2, 1, 5, 6, 2], using this algorithm will result into the result candies = [3, 2, 1, 2, 3, 2]. We get this result by first finding the lowest rating 1, and then go left and right. However, the result is wrong because giving the last child one candy would also meet the distribution requirements, while having a lower number of candies to distribute. Therefore, we need to determine which ratings are local minimum, which will get only one candy.

Solution 1: Local minimums

In order to give the minimum amount of candies, we need to first find out the local minimums. Local minimums will each get one candy. For each local minimum, we go left and right to determine the amount of candies to give to the neighbour. If a neighbour has a higher rating, we will increment the amount of candies to give by one, compare it to the candies the neighbour has already been assigned to and take the larger of the two. If the neighbour has a lower rating, we will stop because the remaining neighbours have been or will be visited from another local minimum.

def getLocalMins(self, ratings):
        localMins = []
        for i in range(len(ratings)):
            if i == 0 and ratings[i] <= ratings[i + 1]:
                localMins.append(i)
            elif i == len(ratings) - 1 and ratings[i] <= ratings[i - 1]:
                localMins.append(i)
            elif ratings[i] <= ratings[i - 1] and ratings[i] <= ratings[i + 1]:
                localMins.append(i)
        return localMins
def candy(self, ratings):
        if len(ratings) == 1: return 1
        localMins = self.getLocalMins(ratings)
        candies = [1] * len(ratings)
        
        for localMin in localMins:
            for i in reversed(range(localMin)):
                if ratings[i] > ratings[i + 1]:
                    candies[i] = max(candies[i], candies[i + 1] + 1)
                else:
                    break
            for i in range(localMin + 1, len(ratings)):
                if ratings[i] > ratings[i - 1]:
                    candies[i] = max(candies[i], candies[i - 1] + 1)
                else:
                    break
                    
        return sum(candies)

Since each rating will be visited maximum twice (from the left and/or from the right), the time complexity is O(n). And to store the array of candies, we need O(n) space.

Time: O(n), Space: O(n)

Solution 2: Two passes

In the previous approach, we first find the local minimums and expand from each of them to the left and to the right. However, we can actually simply this process by iterating through the array twice: once from the left to the right and once from right to the left. If we initialise the array candies to all ones, the first iteration from the left to the right will ensure that for each child, the right neighbour will have more candies if they have a higher rating. And the second pass will do the same for the left neighbour of each child.

def candy(self, ratings):
        candies = [1] * len(ratings)
        
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
                
        for i in reversed(range(0, len(ratings) - 1)):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
        return sum(candies)

The time and space complexity stay the same, but this solution is more succinct.

Time: O(n), Space: O(n)

Hopefully, you have found this article useful.

If you like my stories, don’t forget to give them a clap 👏 .

Please follow me and share the article with your friends! Cheers! 😉