Candy
Candy is a hard arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (two greedy passes), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (fix violations until stable) up.
Problem
There are n children standing in a line, and child i has a rating ratings[i]. You are handing out candies under two rules:
- Every child gets at least one candy.
- A child with a higher rating than an adjacent child must get more candies than that neighbour.
Return the minimum total number of candies you need.
Examples
Example 1
- Input
ratings = [1, 3, 2]- Output
4- Why
- Give 1, 2, 1 candies: the middle child outranks both neighbours, so they get more than each of them.
Example 2
- Input
ratings = [4, 4, 4]- Output
3- Why
- Equal ratings impose no rule, so everyone gets the minimum of 1.
Example 3
- Input
ratings = [5, 4, 3, 2, 6]- Output
12- Why
- The falling run needs 4, 3, 2, 1 candies, and the last child outranks its neighbour, so it gets 2. Total 4 + 3 + 2 + 1 + 2 = 12.
Constraints
1 <= ratings.length <= 2 * 10^40 <= ratings[i] <= 2 * 10^4
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (fix violations until stable) | O(n²) | O(n) |
| Optimal (two greedy passes) | O(n) | O(n) |
1Brute force (fix violations until stable)
O(n²)A value only grows, and each sweep fixes at least one more position of the longest slope, so at most about n sweeps of O(n) each.O(n)One candies array.Start everyone at 1 candy and keep sweeping the line. Whenever a child has a higher rating than a neighbour but not more candies, give them neighbour's candies + 1. Stop when a full sweep changes nothing.
- candies = [1, 1, …, 1].
- Repeat: changed = false; for each i, if ratings[i] > ratings[i - 1] and candies[i] <= candies[i - 1], set candies[i] = candies[i - 1] + 1; same check against i + 1; mark changed.
- When no sweep changes anything, return the sum.
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
boolean changed = true;
while (changed) {
changed = false;
for (int i = 0; i < n; i++) {
if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
candies[i] = candies[i - 1] + 1;
changed = true;
}
if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
changed = true;
}
}
}
int total = 0;
for (int c : candies) total += c;
return total;
}
}class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
candies = [1] * n
changed = True
while changed:
changed = False
for i in range(n):
if i > 0 and ratings[i] > ratings[i - 1] and candies[i] <= candies[i - 1]:
candies[i] = candies[i - 1] + 1
changed = True
if i < n - 1 and ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
candies[i] = candies[i + 1] + 1
changed = True
return sum(candies)class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> candies(n, 1);
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i < n; i++) {
if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
candies[i] = candies[i - 1] + 1;
changed = true;
}
if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
changed = true;
}
}
}
int total = 0;
for (int c : candies) total += c;
return total;
}
};function candy(ratings) {
const n = ratings.length;
const candies = new Array(n).fill(1);
let changed = true;
while (changed) {
changed = false;
for (let i = 0; i < n; i++) {
if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
candies[i] = candies[i - 1] + 1;
changed = true;
}
if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
changed = true;
}
}
}
return candies.reduce((a, b) => a + b, 0);
}2Optimal (two greedy passes)
O(n)Two linear passes plus a sum.O(n)One array of n candy counts.Split the rule into its two halves. A left-to-right pass makes every child beat a lower-rated left neighbour; a right-to-left pass makes every child beat a lower-rated right neighbour while keeping what the first pass required by taking the maximum. Each value is the smallest that satisfies both sides, so the total is minimal.
- candies = [1, …, 1].
- For i from 1 to n - 1: if ratings[i] > ratings[i - 1], candies[i] = candies[i - 1] + 1.
- For i from n - 2 down to 0: if ratings[i] > ratings[i + 1], candies[i] = max(candies[i], candies[i + 1] + 1).
- Return the sum of candies.
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
int total = 0;
for (int c : candies) total += c;
return total;
}
}class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
candies = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
return sum(candies)class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> candies(n, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) candies[i] = max(candies[i], candies[i + 1] + 1);
}
int total = 0;
for (int c : candies) total += c;
return total;
}
};function candy(ratings) {
const n = ratings.length;
const candies = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
}
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
return candies.reduce((a, b) => a + b, 0);
}Edge cases to test
- A single child: 1 candy
- All ratings equal: n candies
- Strictly increasing or strictly decreasing ratings: 1 + 2 + … + n
- Equal neighbours, which do not need to differ, e.g. [1, 2, 2]
- A peak whose two slopes have different lengths
Hints
Hint 1
Each child has two rules: one with the left neighbour and one with the right neighbour. Try satisfying them separately.
Hint 2
Left to right: if ratings[i] > ratings[i - 1], child i needs at least left[i - 1] + 1. Right to left gives the symmetric requirement.
Hint 3
Each child must satisfy both, so the answer for a child is the maximum of the two requirements.
FAQ
What is the best time complexity for Candy?
Optimal (two greedy passes) runs in O(n) time and O(n) extra space. Two linear passes plus a sum.
Which pattern does Candy use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Candy?
Yes. Brute force (fix violations until stable) takes O(n²) time and O(n) space. Start everyone at 1 candy and keep sweeping the line.
Which edge cases should I test for Candy?
A single child: 1 candy; All ratings equal: n candies; Strictly increasing or strictly decreasing ratings: 1 + 2 + … + n; Equal neighbours, which do not need to differ, e.g. [1, 2, 2]; A peak whose two slopes have different lengths.