135.Candy(Hard).md

135. Candy (Hard)

Date and Time: Sep 13, 2024, 10:56 (EST)

Link: https://leetcode.com/problems/candy/

Question:

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.

Example 1:

Input: ratings = [1,0,2]

Output: 5

Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]

Output: 4

Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

• n == ratings.length

• 1 <= n <= 2 * 10^4

• 0 <= ratings[i] <= 2 * 10^4

Walk-through:

1. We are given two requirements, to satisfy the first requirement, we can first initialize an array candy = [1] * len(ratings).

2. Since the children with a higher rating get more candies than their neighbors, we can first loop over ratings from left to right ane detect if an element in ratings is greater than its left neighbor, if so, we update the candy[i] = candy[i-1]+1, because we want to have higher value than its neighbor.

3. We do the same thing from the right to the left and check if an element is greater than its right neighbor. If so, we want to update candy[i] = max(candy[i], candy[i+1]+1), we don't want to replace candy[i] with a value lower than its original candy[i].

4. Finally, we just return the sum of candy[].

Python Solution:

class Solution:
    def candy(self, ratings: List[int]) -> int:
        # Initialize candy[] to be all 1
        # Loop from left to right, if ratings[i] > ratings[i-1], set candy[i] = candy[i-1] + 1
        # Loop from right to left, if ratings[i] > ratings[i+1], set candy[i] = max(candy[i], candy[i+1]+1)

        # TC: O(n), SC: O(n)
        candy = [1] * len(ratings)
        # Update candy from left to right
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                candy[i] = candy[i-1] + 1
        # From right to left
        for i in range(len(ratings)-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                candy[i] = max(candy[i], candy[i+1]+1)
        
        return sum(candy)

Time Complexity: $O(n)$, n is the length of ratings.
Space Complexity: $O(n)$