135. Candy

NeetCode: Candy · LeetCode: 135. Candy · Difficulty: Hard

n children stand in a line, child i has rating ratings[i]. Give candies so that every child gets at least one, and a child with a higher rating than a neighbour gets more candies than that neighbour. Return the minimum total number of candies.

Example

Input:  ratings = [1, 0, 2]          Output: 5   (2, 1, 2)
Input:  ratings = [1, 2, 2]          Output: 4   (1, 2, 1)
Input:  ratings = [1, 3, 2, 2, 1]    Output: 7   (1, 2, 1, 2, 1)

Brute force: repeat until stable

Start everyone at one candy. Sweep the line; whenever a child is rated higher than a neighbour but does not have strictly more candy, raise the child to neighbour + 1. Candies only increase, and the process stops when a sweep changes nothing. A long descending run needs the raise to propagate one step per sweep, so up to n sweeps of O(n) are needed.

import java.util.Arrays;

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 + 1 < n && 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;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.candy(new int[]{1, 0, 2}));
        System.out.println(s.candy(new int[]{1, 2, 2}));
        System.out.println(s.candy(new int[]{1, 3, 2, 2, 1}));
        System.out.println(s.candy(new int[]{5, 4, 3, 2, 1}));
        System.out.println(s.candy(new int[]{}));
    }
}

5
4
7
15
0

The total is an int. It is at most n * (n + 1) / 2, so it overflows only for inputs far larger than the problem's limits. Time: O(n^2). Space: O(n).

Optimal: two passes with an array

Each child has two constraints, one per neighbour, and they can be satisfied independently. A left-to-right pass handles the left neighbour: left[i] = left[i-1] + 1 if the child is rated higher than the left neighbour, otherwise 1. A right-to-left pass does the same for the right neighbour. A child must satisfy both, so the answer for that child is the maximum of the two values, and no smaller number works.

import java.util.Arrays;

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        Arrays.fill(left, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        int[] right = new int[n];
        Arrays.fill(right, 1);
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += Math.max(left[i], right[i]);
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.candy(new int[]{1, 0, 2}));
        System.out.println(s.candy(new int[]{1, 2, 2}));
        System.out.println(s.candy(new int[]{1, 3, 2, 2, 1}));
        System.out.println(s.candy(new int[]{5, 4, 3, 2, 1}));
        System.out.println(s.candy(new int[]{}));
    }
}

5
4
7
15
0

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

Trace for [1, 3, 2, 2, 1]:

ratings  1 3 2 2 1
left     1 2 1 1 1     (only looks at the left neighbour)
right    1 2 1 2 1     (only looks at the right neighbour)
max      1 2 1 2 1  -> 7

O(1)-space follow-up. The ratings form alternating rising and falling slopes, so one pass can replace the arrays. Along a rising slope of length up, the candies are 1, 2, ..., up. Along a falling slope of length down, they are down, ..., 2, 1, which sums to down * (down + 1) / 2. The peak child sits on both slopes and takes max(up, down) candies. Equal neighbours reset the slope counters. Only the current slope lengths are stored, so extra space is O(1) and time stays O(n).

How to explain it in an interview

• Start with the repeated-sweep solution: fix violations until nothing changes, which is O(n^2) in the worst case.
• Observe that the left and right constraints are independent. One pass per direction handles each, and the answer per child is the maximum of the two values.
• Code it in three steps: left = new int[n] filled with 1 and swept left to right, right the same swept right to left, then the sum of Math.max(left[i], right[i]).
• State the complexity: O(n) time and O(n) space for the two arrays.
• Mention the follow-up: O(1) space by tracking the lengths of the current rising and falling slopes, with the peak taking the larger of the two.
• Pitfalls: equal ratings impose no constraint, so the child resets to 1; handle empty input.