Jobs

Interviews

Discussions

Candy

Hard

Amazon

20 views

Topics:

ArraysGreedy Algorithms

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

Candy

Hard

Amazon

20 views

Topics:

ArraysGreedy Algorithms

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values in the `ratings` array? Can they be negative, zero, or very large?
What is the expected behavior if the input `ratings` array is empty or contains only one element?
If two adjacent children have the same rating, do they need to receive the same number of candies, or can they have different amounts as long as they each have at least one?
Is there an upper limit on the size of the `ratings` array? I want to understand potential memory constraints.
Are we looking for the absolute minimum number of candies, or is there a tolerance for a slightly sub-optimal solution if it simplifies the implementation?

Brute Force Solution

Approach

The brute force approach to the candy problem involves trying every single possible candy assignment. We start by giving each child the minimum amount of candy and then methodically explore every possible way to adjust those amounts.

Here's how the algorithm would work step-by-step:

Begin by giving each child one candy to start.
Check if the candy distribution is 'fair' by making sure children with higher ratings get more candy than their neighbors with lower ratings.
If the distribution is not fair, systematically increase the candies given to each child one by one, checking after each adjustment if the distribution has become fair.
Repeat this process of adjusting the number of candies and checking for fairness until all possible combinations of candy assignments have been tried.
Of all the candy distributions that are considered 'fair', choose the one that uses the least amount of total candy.

Code Implementation

def candy_brute_force(ratings):
    number_of_children = len(ratings)
    if number_of_children <= 0:
        return 0

    min_candies = float('inf')

    def is_valid_distribution(candies):
        for index in range(number_of_children):
            # Check left neighbor
            if index > 0 and ratings[index] > ratings[index - 1] and candies[index] <= candies[index - 1]:
                return False

            # Check right neighbor
            if index < number_of_children - 1 and ratings[index] > ratings[index + 1] and candies[index] <= candies[index + 1]:
                return False
        return True

    def generate_distributions(index, current_candies):
        nonlocal min_candies

        if index == number_of_children:
            if is_valid_distribution(current_candies):

                # Only update if its the minimum total number of candies so far
                total_candies = sum(current_candies)
                min_candies = min(min_candies, total_candies)
            return

        # Explore possibilities by adding 1 candy at a time
        for candy_count in range(1, number_of_children * 5 + 1): # Iterate for all possible candy counts
            generate_distributions(index + 1, current_candies + [candy_count])

    generate_distributions(0, [])
    return min_candies

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(infinity) – The provided brute force approach attempts every possible candy assignment until it finds a fair distribution. Because there is no limit on the number of candies a child can receive, and we check every combination, the algorithm will continue indefinitely if a 'fair' distribution that is also the minimal one is never reached or the algorithm has no effective stopping condition. Therefore, the time complexity approaches infinity, as it might never terminate. In a practical sense, without imposed constraints, the algorithm could theoretically run forever.

Space Complexity

O(1) – The brute force approach described primarily involves iteratively adjusting candy counts in place and checking for fairness. It doesn't appear to use any auxiliary data structures like lists, hashmaps, or recursion. The algorithm only requires a few constant space variables, such as counters to track the current candy distribution being explored and a variable to store the minimum fair candy sum found so far. Therefore, the space complexity is O(1) because the memory usage remains constant regardless of the input size, N (the number of children).

Optimal Solution

Approach

This problem asks us to fairly distribute candies to children based on their ratings. The key insight is to ensure each child receives at least one candy and that children with higher ratings get more candies than their immediate neighbors. We can achieve this efficiently by traversing the line of children twice: once from left to right and then from right to left, making local adjustments to the candy distribution.

Here's how the algorithm would work step-by-step:

Give every child one candy to start.
Go through the children from left to right. If a child has a higher rating than the child to their left, give them one more candy than the child to their left.
Now, go through the children from right to left. If a child has a higher rating than the child to their right, make sure they have more candies than the child to their right. But be careful: if they already have enough candies from the first pass, don't reduce the candies they already have.
Add up the number of candies each child has. This is the minimum number of candies needed to satisfy the problem's rules.

Code Implementation

def candy(ratings):
    number_of_children = len(ratings)
    candies = [1] * number_of_children

    # Ensure left neighbors with higher ratings get more candy
    for i in range(1, number_of_children):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    # Ensure right neighbors with higher ratings get more candy
    for i in range(number_of_children - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)

    total_candies = sum(candies)
    return total_candies

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array of children's ratings twice. The first loop traverses from left to right to adjust candy counts based on the left neighbor's rating. The second loop goes from right to left, adjusting candy counts based on the right neighbor's rating while ensuring we keep the maximum candies assigned. Both loops visit each of the n children once. Therefore, the time complexity is proportional to the number of children, resulting in O(n).

Space Complexity

O(N) – The algorithm uses an auxiliary array called 'candies' to store the number of candies allocated to each child. This array has the same length as the input array 'ratings', where N represents the number of children (and the length of the ratings array). Therefore, the space required by the 'candies' array grows linearly with the input size N. No other significant auxiliary data structures are used.

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 because there are no children to distribute candies to.
Array with only one child	Return 1 since only one candy is needed.
Array with two children, ratings are equal	Return 2, each child gets one candy.
Array with two children, one rating higher than other	Return 3; one child gets 1 candy, other gets 2.
Array with all children having the same rating	Each child receives exactly one candy, return the array's length.
Array with monotonically increasing ratings	The candies should increment from 1 to n, so the sum of integers from 1 to n will be the result.
Array with monotonically decreasing ratings	The candies should decrement from n to 1, so the sum of integers from 1 to n will be the result.
Array with a V-shaped rating pattern (one child is lowest rated)	The algorithm correctly handles this, since it iterates both left to right and right to left.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values in the `ratings` array? Can they be negative, zero, or very large?
What is the expected behavior if the input `ratings` array is empty or contains only one element?
If two adjacent children have the same rating, do they need to receive the same number of candies, or can they have different amounts as long as they each have at least one?
Is there an upper limit on the size of the `ratings` array? I want to understand potential memory constraints.
Are we looking for the absolute minimum number of candies, or is there a tolerance for a slightly sub-optimal solution if it simplifies the implementation?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Begin by giving each child one candy to start.
Check if the candy distribution is 'fair' by making sure children with higher ratings get more candy than their neighbors with lower ratings.
If the distribution is not fair, systematically increase the candies given to each child one by one, checking after each adjustment if the distribution has become fair.
Repeat this process of adjusting the number of candies and checking for fairness until all possible combinations of candy assignments have been tried.
Of all the candy distributions that are considered 'fair', choose the one that uses the least amount of total candy.

Code Implementation

def candy_brute_force(ratings):
    number_of_children = len(ratings)
    if number_of_children <= 0:
        return 0

    min_candies = float('inf')

    def is_valid_distribution(candies):
        for index in range(number_of_children):
            # Check left neighbor
            if index > 0 and ratings[index] > ratings[index - 1] and candies[index] <= candies[index - 1]:
                return False

            # Check right neighbor
            if index < number_of_children - 1 and ratings[index] > ratings[index + 1] and candies[index] <= candies[index + 1]:
                return False
        return True

    def generate_distributions(index, current_candies):
        nonlocal min_candies

        if index == number_of_children:
            if is_valid_distribution(current_candies):

                # Only update if its the minimum total number of candies so far
                total_candies = sum(current_candies)
                min_candies = min(min_candies, total_candies)
            return

        # Explore possibilities by adding 1 candy at a time
        for candy_count in range(1, number_of_children * 5 + 1): # Iterate for all possible candy counts
            generate_distributions(index + 1, current_candies + [candy_count])

    generate_distributions(0, [])
    return min_candies

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Give every child one candy to start.
Go through the children from left to right. If a child has a higher rating than the child to their left, give them one more candy than the child to their left.
Now, go through the children from right to left. If a child has a higher rating than the child to their right, make sure they have more candies than the child to their right. But be careful: if they already have enough candies from the first pass, don't reduce the candies they already have.
Add up the number of candies each child has. This is the minimum number of candies needed to satisfy the problem's rules.

Code Implementation

def candy(ratings):
    number_of_children = len(ratings)
    candies = [1] * number_of_children

    # Ensure left neighbors with higher ratings get more candy
    for i in range(1, number_of_children):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    # Ensure right neighbors with higher ratings get more candy
    for i in range(number_of_children - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)

    total_candies = sum(candies)
    return total_candies

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 because there are no children to distribute candies to.
Array with only one child	Return 1 since only one candy is needed.
Array with two children, ratings are equal	Return 2, each child gets one candy.
Array with two children, one rating higher than other	Return 3; one child gets 1 candy, other gets 2.
Array with all children having the same rating	Each child receives exactly one candy, return the array's length.
Array with monotonically increasing ratings	The candies should increment from 1 to n, so the sum of integers from 1 to n will be the result.
Array with monotonically decreasing ratings	The candies should decrement from n to 1, so the sum of integers from 1 to n will be the result.
Array with a V-shaped rating pattern (one child is lowest rated)	The algorithm correctly handles this, since it iterates both left to right and right to left.