135. Candy

Hard

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.

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 * 104
0 <= ratings[i] <= 2 * 104

Solutions

Approach: Greedy

Time complexity: \(O(n)\)

Space complexity: \(O(n)\)

Way 1:

Algorithmic Way

We initialize a candies array with 1 candy for each child.

First, we go left to right: if a child has a higher rating than the one before, they get one more candy.

Then, we go right to left: if a child has a higher rating than the one after, we ensure they have more candies by taking the max of current and one more than the next.

Finally, we sum all candies and return the total.

Time complexity O(n) , Space complexity O(n).Where n is the number of children.

Python

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n
        # Left to right pass
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
        # Right to left pass
        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)

Way 2:

Notes

We initialize two arrays L and R, where L[i] represents the minimum number of candies the current child should get when the current child's score is higher than the left child's score, and R[i] represents the minimum number of candies the current child should get when the current child's score is higher than the right child's score. Initially, L[i] = 1, R[i] = 1.

We traverse the array from left to right once, and if the current child's score is higher than the left child's score, then L[i] = L[i - 1] + 1;

Similarly, we traverse the array from right to left once, and if the current child's score is higher than theright child's score, then R[i] = R[i+1] + 1. Finally, we traverse the array of scores once, and the minimum number of candies each child should get is the maximum of L[i] and R[i], and we add them up to get the answer.

Time complexity O(n), space complexity O(n). Where n is the length of the array of scores.

Python

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        L = [1]*n
        R = [1]*n
        ans = 0
        for i in range(1,n):
            if ratings[i]>ratings[i-1]:
                L[i] = L[i-1] +1

        for i in range(n-2,-1,-1):
            if ratings[i]>ratings[i+1]:
                R[i] = R[i+1] + 1

        for l,r in zip(L,R):
            ans+=max(l,r)

        return ans