Problem Description
There are n children standing in line, each with a rating value provided in an array. The goal is to distribute candies such that each child receives at least one candy and any child with a higher rating than an adjacent child gets more candies than that neighbor. Return the minimum number of candies needed to fulfill these requirements.
Key Insights
- Every child must get at least one candy.
- A left-to-right pass ensures that each child has more candies than the left neighbor if their rating is higher.
- A right-to-left pass ensures that each child has more candies than the right neighbor if their rating is higher.
- The final candy distribution for each child is determined by taking the maximum candies assigned by the two passes.
Space and Time Complexity
Time Complexity: O(n) - Two passes over the array, each in linear time. Space Complexity: O(n) - An auxiliary array is used to store the candy counts for each child.
Solution
We start by initializing an array with 1 candy for each child, since each child must receive at least one candy. Then, perform a left-to-right pass: if a child’s rating is higher than the previous child, assign one more candy than the previous child. Next, perform a right-to-left pass: if a child’s rating is higher than the next child, update the candy count to be the maximum of its current value or one more than the next child's candy count. The answer is the sum of the adjusted candy counts.