Fair Candy Shares
Problem
Children stand in a row and each has a score. Every child must get at least one sweet, and a child whose score is higher than a direct neighbour's must get more sweets than that neighbour. Equal scores place no demand either way. Return the smallest total number of sweets that meets both rules.
Examples
Input: scores = [1, 0, 2]
Output: 5
Why: hand out 2, 1, 2Input: scores = [1, 2, 2]
Output: 4
Why: hand out 1, 2, 1; the last child only has to beat nobodyInput: scores = [7]
Output: 1
Why: edge case, a lone child still needs one sweetHints
0 / 3
Each child is constrained by two neighbours, and fixing one side can break the other. Try handling the two sides separately.
A single left-to-right pass can satisfy every rule that compares a child with the child on their left. A second pass in the other direction can do the same for the right, as long as it does not undo the first.
Start everyone at one. Sweep left to right, giving a child one more than their left neighbour whenever their score is higher. Then sweep right to left, raising a child to one more than their right neighbour when their score is higher, keeping the larger of the two amounts. Sum the list.
Solution
The left-to-right pass gives each child exactly the length of the rising run that ends at them, which is the least that satisfies every left-neighbour rule. The right-to-left pass computes the same for the right side, and taking the maximum of the two meets both rules at once; neither pass hands out a sweet that some rule does not force, so the total is minimal. The maximum is what stops the second pass from undoing the first. Time is O(n) over two sweeps and space is O(n) for the counts.
def fewest_sweets(scores):
n = len(scores)
give = [1] * n # everyone gets at least one
for i in range(1, n): # rules against the left neighbour
if scores[i] > scores[i - 1]:
give[i] = give[i - 1] + 1
for i in range(n - 2, -1, -1): # rules against the right neighbour
if scores[i] > scores[i + 1]:
give[i] = max(give[i], give[i + 1] + 1) # keep the left rule intact
return sum(give)
print(fewest_sweets([1, 0, 2])) # -> 5
print(fewest_sweets([1, 2, 2])) # -> 4
print(fewest_sweets([7])) # -> 1
print(fewest_sweets([1, 3, 4, 5, 2])) # -> 11Stuck on the idea rather than the code? What Makes Greedy Work covers it.