Distribute Candy

Children stand in a line, each with a rating. Give out candies so that:

every child gets at least one candy, and
a child with a higher rating than a neighbour gets more candies than that neighbour.

Return the minimum total number of candies.

Example

Text

ratings = [1, 0, 2]   ->  5   (candies 2, 1, 2)
ratings = [1, 2, 2]   ->  4   (candies 1, 2, 1: equal ratings need nothing)

Brute force: fix violations until none are left

Start with one candy each. Sweep the line, and whenever a child has a higher rating than a neighbour but not more candies, give them one more than that neighbour. Repeat until a sweep changes nothing.

Java

import java.util.Arrays;

public class Main {
    static 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 + 1 < n && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                    candies[i] = candies[i + 1] + 1;
                    changed = true;
                }
            }
        }
        return Arrays.stream(candies).sum();
    }

    public static void main(String[] args) {
        System.out.println(candy(new int[]{1, 0, 2}) + " " + candy(new int[]{1, 2, 2}));
        System.out.println(candy(new int[]{5, 4, 3, 2, 1}));
    }
}

Output

5 4
15

Time: O(n²): a decreasing run needs one sweep per child to propagate. Space: O(n).

Optimal: two passes

Each child's count has to satisfy the left neighbour and the right neighbour, and the two constraints can be handled separately:

Left to right: if ratings[i] > ratings[i - 1], set left[i] = left[i - 1] + 1, else 1. This is the minimum that satisfies every left-neighbour rule.
Right to left: the same for the right neighbour, giving right[i].
Each child needs max(left[i], right[i]): enough for both sides, and no more.

The second pass can update the first pass's array in place, so only one array is needed. Arrays.fill sets every element of an array to one value, and Arrays.stream(candies).sum() adds the elements of an int[].

rating	1	3	4	5	2
left pass	1	2	3	4	1
right pass	1	1	1	2	1
candies (max)	1	2	3	4	1

Java

import java.util.Arrays;

public class Main {
    static 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);
            }
        }
        return Arrays.stream(candies).sum();
    }

    public static void main(String[] args) {
        System.out.println(candy(new int[]{1, 0, 2}) + " " + candy(new int[]{1, 2, 2}));
        System.out.println(candy(new int[]{5, 4, 3, 2, 1}) + " " + candy(new int[]{1, 3, 4, 5, 2}));
        System.out.println(candy(new int[]{7}) + " " + candy(new int[]{}));
    }
}

Output

5 4
15 11
1 0

Time: O(n). Space: O(n).

Edge cases

Single child: 1. No children: 0, since the loops do not run and the sum of an empty array is 0.
Equal neighbours: no constraint between them, so a child can have fewer candies than an equally rated neighbour.
Strictly decreasing ratings: n, n - 1, ..., 1, found by the right-to-left pass.