Coding

Candy

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

A line of N kids is standing there. The rating values listed in the integer array ratings are assigned to each kid.

These kids are receiving candy, according to the following criteria:

There must be at least one candy for every child.
Kids whose scores are higher than their neighbours receive more candies than their neighbours.

Return the minimum number of candies needed to distribute among children.

Input : ratings = [1, 0, 5]

Output : 5

Explanation : The distribution of candies will be 2 , 1 , 2 to first , second , third child respectively.

Input : ratings = [1, 2, 2]

Output : 4

Explanation : The distribution of candies will be 1 , 2 , 1 to first , second , third child respectively. The third gets only 1 candy because it satisfy above two criteria.

Input : ratings = [1, 2, 1, 4, 5]

1 <= n <= 104
0 <= ratings[i] <= 105

cpp

class Solution {
public:
    int candy(vector<int>& ratings) {
        //your code goes here
    }
};

java

class Solution {
    public int candy(int[] ratings) {
       //your code goes here
    }
}

python

class Solution:
    def candy(self, ratings):
        #your code goes here

javascript

class Solution {
    candy(ratings) {
        //your code goes here
    }
}

csharp

public class Solution {
    public int Candy(int[] ratings) {

    }
}

func candy(ratings []int) int {

}

Stuck? Show a way to structure it+

01Initialize all candies to one
02Satisfy rising slopes from the left
03Satisfy descending slopes from the right with max
04Sum after both constraints are met

Reference answer

Start by restating the input contract for Candy and testing the smallest boundary case before choosing the algorithm. Give every child one candy initially. Make a left-to-right pass so a child with a higher rating than its left neighbor gets one more, then a right-to-left pass enforcing the analogous right constraint with max(current, right+1). Sum the resulting counts. Explain the invariant while coding, then show how each update preserves it. The two passes are O(n) time and the described candy array uses O(n) space. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

Can this be solved in O(1) extra space?
Tests: complexity analysis
Why does taking max satisfy both neighbors?
Tests: correctness reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question