Candy

Hard Arrays & Hashing Greedy Original on LeetCode

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^4
  • 0 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (fix violations until stable)O(n²)O(n)
Optimal (two greedy passes)O(n)O(n)

1Brute force (fix violations until stable)

TimeO(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.
SpaceO(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.

  1. candies = [1, 1, …, 1].
  2. 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.
  3. 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;
    }
}

2Optimal (two greedy passes)

TimeO(n)Two linear passes plus a sum.
SpaceO(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.

  1. candies = [1, …, 1].
  2. For i from 1 to n - 1: if ratings[i] > ratings[i - 1], candies[i] = candies[i - 1] + 1.
  3. For i from n - 2 down to 0: if ratings[i] > ratings[i + 1], candies[i] = max(candies[i], candies[i + 1] + 1).
  4. 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;
    }
}

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.