135. Candy - Explanation

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 = [4,3,5]

Output: 5

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

Example 2:

Input: ratings = [2,3,3]

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:

1 <= ratings.length <= 20,000
0 <= ratings[i] <= 20,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        arr = [1] * n

        for i in range(n - 1):
            if ratings[i] == ratings[i + 1]:
                continue
            if ratings[i + 1] > ratings[i]:
                arr[i + 1] = arr[i] + 1
            elif arr[i] == arr[i + 1]:
                arr[i + 1] = arr[i]
                arr[i] += 1
                for j in range(i - 1, -1, -1):
                    if ratings[j] > ratings[j + 1]:
                        if arr[j + 1] < arr[j]:
                            break
                        arr[j] += 1

        return sum(arr)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Greedy (Two Pass)

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        arr = [1] * n

        for i in range(1, n):
            if ratings[i - 1] < ratings[i]:
                arr[i] = arr[i - 1] + 1

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

        return sum(arr)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Greedy (One Pass)

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        res = n

        i = 1
        while i < n:
            if ratings[i] == ratings[i - 1]:
                i += 1
                continue

            inc = 0
            while i < n and ratings[i] > ratings[i - 1]:
                inc += 1
                res += inc
                i += 1

            dec = 0
            while i < n and ratings[i] < ratings[i - 1]:
                dec += 1
                res += dec
                i += 1

            res -= min(inc, dec)

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.