HardGreedy
Candy
Minimum candies for children
Solution Approach
Two passes: left-to-right and right-to-left. Ensure higher rating gets more candy than neighbors.
Implementation
def distributeCandies(ratings):
n = len(ratings)
candies = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
return sum(candies)Complexity Analysis
Time Complexity
O(n)Space Complexity
O(n)Complexity
Time:O(n)
Space:O(n)
Asked at
GoogleAmazonFacebook