# 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.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Assign Mice to Holes | InterviewBit | Solution Explained

June 13, 2022

2. This solution need an amendment for 2 digit number.

3. Please write a Proof for this

4. Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.

A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.

Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.

To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.

Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.

This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.

This site uses Akismet to reduce spam. Learn how your comment data is processed.