Problem Description
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Key Insights
- Each child must receive at least one candy.
- If a child has a higher rating than a neighbor, they must receive more candies than that neighbor.
- A two-pass approach can be used to ensure both conditions are met.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Solution
To solve this problem, we can use a greedy algorithm with a two-pass approach. First, we initialize an array of candies where each child receives one candy. In the first pass, we traverse the ratings from left to right, ensuring that if a child has a higher rating than the previous child, they receive more candies. In the second pass, we traverse from right to left to ensure the same condition for the neighbors on the right. Finally, we sum up the candies to get the minimum required.