Children stand in a line and child i has a rating ratings[i]. Give each child at least one candy, and any child with a higher rating than a direct neighbour must get more candies than that neighbour. Return the minimum total number of candies.
- 1 <= ratings.length <= 2 * 10^4
- 0 <= ratings[i] <= 2 * 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A naive fix is to keep scanning and bumping up children who break a rule until nothing changes, which can be O(n^2). Split the condition instead. Pass 1 (left to right): if ratings[i] > ratings[i-1], child i needs left[i-1] + 1, else 1. Pass 2 (right to left): if ratings[i] > ratings[i+1], child i needs right[i+1] + 1, else 1. Each child must satisfy both, so it gets max(left[i], right[i]). This is the minimum because each pass gives the smallest value its rule allows, and taking the max does not break the other side: raising a peak only makes its "greater than neighbour" condition stronger.
Algorithm
- Create
candyfilled with 1. - Left to right: if
ratings[i] > ratings[i-1], setcandy[i] = candy[i-1] + 1. - Right to left: if
ratings[i] > ratings[i+1], setcandy[i] = max(candy[i], candy[i+1] + 1). - Return the sum of
candy.
O(n)Space: O(n)[1,2,2] needs 4, not 5. Students who use >= instead of > get this wrong. An O(1) space version that counts up and down slopes exists and is a popular follow-up.class Solution: def candy(self, ratings: List[int]) -> int: n = len(ratings) candy = [1] * n for i in range(1, n): # left neighbour rule if ratings[i] > ratings[i - 1]: candy[i] = candy[i - 1] + 1 for i in range(n - 2, -1, -1): # right neighbour rule if ratings[i] > ratings[i + 1]: candy[i] = max(candy[i], candy[i + 1] + 1) return sum(candy)