Children stand in a line, each with a rating. Each child gets at least one candy, and a child with a higher rating than a neighbour must get more than that neighbour.
DSA Animator › DSA Revision › Greedy › Candy
Remember: split a two-sided rule into two one-sided passes. Take the maximum so both rules hold. The video solves Candy (LeetCode 135, Hard) with the Two-Pass Greedy pattern from the Greedy topic, and you can replay every step in the interactive Candy animation.
Children stand in a line, each with a rating. Each child gets at least one candy, and a child with a higher rating than a neighbour must get more than that neighbour.
For ratings 1, 3, 2, 2, 1, the candies are 1, 2, 1, 2, 1. The minimum total is 7.
Repeatedly fixing violations until none remain can take O of n squared. Each child really has two separate rules, one for the left neighbour and one for the right.
Give everyone 1 candy to start. Left to right, if a rating is higher than the left neighbour, give one more than that neighbour. Right to left, if a rating is higher than the right neighbour, take the bigger of its value and the right neighbour plus 1.
Start with 1, 1, 1, 1, 1. Left pass: 3 beats 1, so it gets 2, and the rest stay 1, giving 1, 2, 1, 1, 1. Right pass: the second 2 beats the 1 on its right, so it rises to 2. The first 2 does not beat the 2 on its right, and the 3 keeps its 2. The candies are 1, 2, 1, 2, 1, for a total of 7.
In code, fill an array with ones. The first loop handles the left neighbour rule. The second loop goes backwards and takes the maximum for the right neighbour rule. Sum the array, so it's O of n time and O of n space.
Remember: split a two-sided rule into two one-sided passes. Take the maximum so both rules hold.