The Question
Coding

Minimum Candy Distribution

Given an array of integers representing ratings of $n$ children in a line, determine the minimum number of candies required to satisfy two conditions: 1) Each child must receive at least one candy. 2) A child with a higher rating than an adjacent neighbor must receive more candies than that neighbor. Implement an efficient solution and discuss its time and space complexity.
Java
Greedy
Array
Questions & Insights

Clarifying Questions

What are the constraints on the size of the ratings array and the maximum value of each rating? (Assumption: N up to 10^5, ratings are non-negative integers).
If two adjacent children have the same rating, is there a requirement for their candy distribution? (Assumption: No, the "more candies" rule only applies if one rating is strictly greater than the other).
Are the ratings guaranteed to be non-empty? (Assumption: If empty, the result is 0; if N=1, the result is 1).

Thinking Process

Greedy Approach (Left-to-Right): To satisfy the condition for the left neighbor, we can iterate from left to right. If a child's rating is higher than the previous child, they must have at least one more candy than the previous child. Otherwise, the minimum they can have is 1.
Greedy Approach (Right-to-Left): The first pass only considers the left neighbor. To satisfy the condition for the right neighbor, we iterate from right to left. If a child's rating is higher than the next child, they must have more candies than that child. We take the maximum of their current candy count (from the first pass) and the count required by the right neighbor (candies[i+1] + 1).
Optimization: This two-pass approach ensures that both neighbor constraints are met with the minimum possible candies at each step.
Summation: The final answer is the sum of the elements in the distribution array.
Implementation Breakdown

Problem Set

Input: int[] ratings representing the rating of n children.
Functional Requirements:
Every child gets \ge 1 candy.
If ratings[i] > ratings[i-1], then candies[i] > candies[i-1].
If ratings[i] > ratings[i+1], then candies[i] > candies[i+1].
Constraint: Minimize \sum candies.
Complexity Goal: O(N) Time and O(N) Space.

Approach

Algorithm: Two-pass Greedy
Data Structure: Integer Array
Complexity:
Time: O(N) - We traverse the array twice.
Space: O(N) - To store the candy count for each child.

Implementation

Wrap Up

Advanced Topics

Space Optimization: It is possible to solve this in O(1) space using the "Slope Method" (or Peak-Valley approach). We track the length of upward and downward slopes. When we encounter a downward slope, we might need to adjust the height of the preceding peak if the valley becomes too deep.
Parallelization: For extremely large N, the array could be partitioned. However, the dependencies (neighbor ratings) require careful handling at the boundaries, making a simple parallel sum difficult without a multi-pass synchronization strategy.
Readability: While O(1) space is more efficient, the Two-pass Greedy approach is significantly more maintainable and less prone to off-by-one errors, making it the preferred choice in most production environments unless memory is the primary bottleneck.