Distribute Candy | InterviewBit | Solution Explained

I explain the solution to Distribute Candy on InterviewBit using visuals in simple words.

0. Distribute Candy: Problem Discussion

0.0. IO Format

• input:
  • an array of ratings of N kids, who stand in a line
• conditions:
  • each kid gets at least one candy
  • kids with ratings higher than their neighbours get more candies
• output:
  • find the minimum number of candies required to satisfy both the conditions

0.1. Examples

In the case above, we have the ratings of each kid as [1,3,7,1] and we assign them [1,2,3,1] candies respectively. This follows both the conditions mentioned in the question.

1. Distribute Candy: Observations & Logic

1.0. Intuitions

First and foremost, in the test case [1,3,7,1], we realize that we can give each of these kids [1,3,7,1] candies by default. This follows both the conditions in the problem. However, this does not minimize the number of candies. So, we will have to tread carefully.

Now, one solution that comes up immediately is that we can start off with assigning 1 candy to the first kid, and proceed in an iterative fashion. If the value of the current kid is greater than the previous, we assign it one more candy. Otherwise, we can default it back to 1.

Using this logic, we get the correct answer for the test case mentioned!

1.1. Left to right or right to left?

Whenever we have a hypothesis like the one mentioned on top right of the image, we should try our best to disprove it (as I have been saying for the last 1337 blogs).

Let’s consider another example, and this time, try working out the solution on your own.

Here’s the solution.

We see that the first value increases, but the rest decrease.

Now, if you notice, this is not following the condition of neighbours. That is, look at the kid with value 3. That kid is only getting one candy, but has a higher rating than kid of value 1.

This means that kid with value 3 will actually get 2 candies.

We now follow the same logic for the kid with the value 4 and then 7.

In a way, we have propagated the changes from the right to left.

But now, what do we follow? Left to right OR right to left?

1.2. Neither!

What we do instead is smarter. We start form the lowest rating kids. By definition, there is no other kid in the line lower than them – so we can assign them the default value of 1.

Then, we go up the ladder, following the condition: if the kid has higher rating than its neighbour, we increase its count. In this way, if it has higher rating neighbours, we don’t worry about them just yet. They anyways don’t change the answer for the current kid. However, those with lower ratings have already been dealt with. This makes the greedy solution work optimally.

Now, before you jump in the code, try out your understanding on the test case below.

Here’s the solution. If you are confused on how I got to it, look at the video solution on YouTube.

2. Distribute Candy: Optimized Implementation

2.0. Code

class Solution:
    # @param A : list of integers
    # @return an integer
    def candy(self, A):
        n = len(A)
        data = sorted((x, i) for i, x in enumerate(A))
        
        candies = [1] * n

        for _, i in data:
            if i > 0 and A[i] > A[i-1]:
                candies[i] = max(candies[i], candies[i-1] + 1)
            
            if i < n - 1 and A[i] > A[i+1]:
                candies[i] = max(candies[i], candies[i+1] + 1)
        
        return sum(candies)

2.1. Complexity Analysis

• Time: O(NlogN), for sorting
• Space: O(NlogN), if an algorithm like merge sort is used. Most languages have better implementations. Python3 uses Timsort, which runs in O(N) space.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.