Only one problem solution for this week, too much homework..

135 Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

My accepted code can be found here

This problem is trickier than I thought and have a lot of edge case to handle, but sadly I didn’t come up with a simpler and neater solution, and here I share my thoughts.

First thing first we should notice that the problem doesn’t mention anything about a tie of rate. So there isn’t any limitation of the amount of candies given to neighbours of the same rating.

The basic idea is that when we are scanning the array, we want to give as few candies as possible to the current children (how stingy we are). So if current rating is lower than the previous, we give current child 1 candy and increase the candy before this one appropriately, if higher, than we give one more candy than the previous one.

But the actual algorithm is a lot more subtle than the simplest thought:

Candy(ratings: int[]): int:
    if length(ratings) <= 1:
        return length(ratings)

    let result = 1, down = up = 1, prevDown = true
    for i = 1 to length(ratings) - 1: // skip the first one
        if ratings[i] <= ratings [i - 1]:
            if not prevDown:
                prevDown = true
                down = 1
            // if is almost larger than the previous highest one
            else if down == up - 1
                down = up + 1

            // if equal, then initialize down and up
            if ratings[i] == ratings[i - 1]:
                down = up = 1

            result += down
        else: // current larger than previous
            if prevDown:
                prevDown = false
                up = 1
            ++up
            result += up

The down and up represents currently how many ratings are descending / ascending continuously. And we need to detect the first descension or ascension to initialize down and up correspondingly. Another tricky thing is that we should remember the previous most candies child, in case of we should give more candies to his/her neighbour with less rating.

The algorithm runs in O(n) time since it’s only a single scan. And it beats 98% solutions.