Leetcode solution 135: Candy

Problem Statement 

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?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube
• B站

Thought Process

The straight forward idea is go through the ranking array, for each ranking, we try to make sure it has more points than its left and right neighbor. Note that it’s not going to work if you just do that because while you are increasing the values, it’s a chain effect that will affect the previous values as well, therefore we have to go all the way to the beginning.

Use below ranking as an example, assume everyone has 1 point already
Ranking: [5, 3, 1]

Points [1, 0, 0]
When at 5, [1, 0, 0]
When at 3, [2, 1, 0]
When at 1, [2, 2, 1]
you might think 5 points is enough, but it’s wrong. The culprit is when you at 1, and increase child at 3, you have the potential to break the assumption that child with 3 ranking always has less than its left neighbor if that neighbor has more points. Therefore, we have to go all the way to the beginning and comparison, thus resulting O(N^2) time complexity

That said, we have to go all the way to the beginning when we increase any value, so in the end it looks like [3, 2, 1]

Hint: if you cannot solve it in one pass, can we solve it in two passes?

A more clever thought is trying to distribute the candies in two passes. Previously we are trying to ensure at certain point both the left and right constrains should met. With two passes, namely first pass (from left to right) ensure all the left neighbors constrains are satisfied, and second pass ensures all the right neighbors contains are satisfied.

• Left to right pass: Ensure I have more points than my left neighbor if my ranking is higher. Else I just have 1 candy (this is minimum)
• Right to left pass: Ensure I have more points than my right neighbor if my ranking is higher.

Solutions

Naive solution 

Time Complexity: O(N^2)
Space Complexity: O(N) the extra candies array

Two pass linear solution

Time Complexity: O(N)
Space Complexity: O(N) the extra candies array

References

• Leetcode discussion solution