Candy

Hard#135two passes

Children stand in a row, each with a rating. Give them candies: everyone gets at least one, and a child rated higher than a neighbour gets more than that neighbour. Find the fewest candies in all. Our example: [2, 4, 3, 5, 2, 1, 1, 3] — the answer is 13: [1, 2, 1, 3, 2, 1, 1, 2].

135 CandyWalkthrough · 1×

Example: [2, 4, 3, 5, 2, 1, 1, 3]. The top row is the ratings, the arc compares i with a neighbour; the bottom row is the candies.

ratings0214233542516173candies
child ithe neighbour compared withcandies so farcandies just changed

8 children in a row

01/37
restart · back · play · step
Speed
1function candy(ratings):
2 n = len(ratings)
3 candies = [1] * n
4 for i from 1 to n - 1:
5 if ratings[i] > ratings[i - 1]:
6 candies[i] = candies[i - 1] + 1
7 for i from n - 2 down to 0:
8 if ratings[i] > ratings[i + 1]:
9 candies[i] = max(candies[i], candies[i + 1] + 1)
10 return sum(candies)
state
n
8
i
–
candies
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The rule has two sides, and each pass settles one. Left to right, every child gets the fewest candies that satisfy the left neighbour, given what that neighbour already has.
  2. Right to left, max(candies[i], candies[i + 1] + 1) adds the right side without breaking the left one: a count only grows, and growing never hurts a child that must have more than its left neighbour.
  3. Each count is the length of the longest rising run that ends at the child, from the left or from the right, whichever is longer; no valid sharing can give less.

Complexity

Time O(n): two passes over the row. Memory O(n) for the candies.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.