[Leetcode] Candy

Problem

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?

Algorithm

Brute Force O(n^2)

At beginning, we give each child one candy. Then, we iterate the array, and give each unhappy child one more candy. After n times iteration, all children will be happy. 

Divide-and-Conquer O(n*Log(n))

Divide the array into two halves. Recursively compute the minimum candies required in each half. When combine, we need to check whether the two children at the  connection point satisfy the requirement. If not, we need to adjust the higher rating side. 

Peak and Valley O(n)

I was struggled with this algorithms for days, and I think it is not a good approach. 

We can find all the peaks and valleys of the array, based on their ratings. If a child has a valley rating, he/she only needs one candy. Starting from this valley child,  we can move towards the peak. Whenever we see a higher rating child, we raise the number of candies by one. However, each peak may be approached from two valleys, and the minimum candies required by the peak is determined by the farther adjacent valley. 

The implementation of this algorithm is not easy. First we need to consider the boundary conditions, i.e. the beginning and ending of the array. Second, the array may have duplicate values, which makes it harder to determine the peak and valley. 

Left and Right O(n)

Let's change the requirement of the problem, instead of requiring

• Children with a higher rating than their neighbors get more candies,

 we consider

• Children with a higher rating than their left neighbors get more candies,

Then, the problem becomes much easier. We just maintain an array called L, where L[i] is the minimum candies needed for child i. Scan from left to right, L[0] = 1, since for leftmost child there is not pressure from left. 

                          L[i] = L[i-1] + 1             if A[i] > A[i-1]

                                          1                   else

Similarly, we can compute R, where R satisfies "Children with a higher rating than their right neighbors get more candies". 

Once we calculated L and R, 

                          the minimum candies required by child i = max(L[i], R[i]). 

For example, 

A = [1, 2, 2, 3, 4, 1, 2].

L = [1, 2, 1, 2, 3, 1, 2].

R = [1, 1, 1, 1, 2, 1, 1].

Further thought:

In this problem, each element has two constraints, one comes from left and another comes from right. We can separate two constraints, solving them independently. Finally, a linearly combination can resolve the original problem. Some more examples should be found in this kind of questions. 

Code