Practice/PayPal/Leetcode 135. Candy

Leetcode 135. Candy

CodingMust

Problem

You are organizing a competition where children stand in a line, each assigned a performance rating. You need to distribute rewards to the children following these rules:

1. Every child must receive at least one reward
2. Any child with a strictly higher rating than an adjacent neighbor must receive more rewards than that neighbor

Your goal is to determine the minimum total number of rewards needed to satisfy these constraints.

Requirements

1. Return the minimum total number of rewards required
2. Each child must receive at least 1 reward
3. If a child has a higher rating than their immediate neighbor(s), they must receive strictly more rewards than that neighbor
4. Children with equal ratings are NOT required to have equal rewards (only the "higher rating → more rewards" rule applies)

Constraints

• 1 ≤ ratings.length ≤ 20,000
• 0 ≤ ratings[i] ≤ 20,000
• Time complexity should be O(n) where n is the number of children
• Space complexity should be O(n)

Examples

Example 1:

Input: ratings = [1, 2, 3] Output: 6 Explanation: An optimal reward distribution is [1, 2, 3]. Each child has a higher rating than their left neighbor and receives more rewards accordingly. Total: 1 + 2 + 3 = 6

Example 2:

Input: ratings = [3, 2, 1] Output: 6 Explanation: An optimal reward distribution is [3, 2, 1]. Each child has a lower rating than their left neighbor and receives fewer rewards accordingly. Total: 3 + 2 + 1 = 6

Example 3:

` Input: ratings = [1, 0, 2] Output: 5 Explanation: An optimal reward distribution is [2, 1, 2].

• Child at index 0 (rating=1) has higher rating than child at index 1 (rating=0), so gets 2 > 1 rewards
• Child at index 2 (rating=2) has higher rating than child at index 1 (rating=0), so gets 2 > 1 rewards Total: 2 + 1 + 2 = 5 `

Example 4:

Input: ratings = [1, 2, 2, 5, 4, 3, 2] Output: 12 Explanation: One optimal distribution is [1, 2, 1, 4, 3, 2, 1]. Note that children with equal ratings (indices 1 and 2 both have rating=2) can receive different rewards.