#135

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Candy

The Candy problem is a greedy algorithm challenge where you need to minimize candy distribution while satisfying certain rating conditions.

array greedy

Problem Statement

You are given a list of ratings for n children standing in a line. Each child has a rating value provided in the integer array ratings. The goal is to distribute candies to each child such that children with higher ratings receive more candies than their immediate neighbors.

The challenge is to determine the minimum number of candies needed to satisfy these conditions, considering that each child must receive at least one candy. You need to find the optimal solution with a minimal number of candies required while respecting these constraints.

Examples

Example 1

Input: ratings = [1,0,2]

Output: 5

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

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

Solution Approach

Greedy Approach with Left-to-Right Pass

First, initialize an array of candies, where each child receives one candy. Then, traverse the ratings array from left to right, and for each child, if their rating is higher than the previous child, increase their candy count accordingly.

Right-to-Left Pass to Adjust Candies

After the left-to-right pass, perform another pass from right to left. This ensures that children with higher ratings compared to their right neighbor get more candies. You must update the candy allocation while respecting the previous assignments.

Final Candy Calculation

The final solution involves summing up the candy counts from both passes. The sum represents the minimum candies required to satisfy the conditions. The greedy choice in both passes ensures that the candies are distributed optimally while minimizing the total.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n), where n is the number of children. This is because we traverse the list twice: once from left to right and once from right to left. The space complexity is O(n) due to the storage required for the candies array, which holds the candy count for each child.

What Interviewers Usually Probe

Look for a clear understanding of greedy algorithms and how to implement the left-to-right and right-to-left passes.
Test the candidate’s ability to minimize the number of candies through an optimal distribution while respecting the invariant.
Expect the candidate to handle edge cases such as consecutive children with equal ratings or large arrays efficiently.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly handle the right-to-left pass, potentially leading to incorrect candy assignments.
Not initializing candies properly or misunderstanding the invariant conditions for rating comparisons.
Omitting edge cases, such as when all ratings are equal or when there's only one child.

Follow-up variants

Extend the problem by requiring the solution to work for multiple test cases.
Modify the problem to allow varying minimum candy distributions, such as children with ratings greater than 5.
Increase the constraints by considering very large input sizes, testing the efficiency of the algorithm further.

FAQ

How does the greedy approach work in the Candy problem?

The greedy approach works by allocating one candy per child, then adjusting the candy counts based on ratings in two passes: left-to-right and right-to-left.

What are common pitfalls when solving the Candy problem?

Common pitfalls include missing the right-to-left pass, failing to correctly handle the candy initialization, and not accounting for edge cases like equal ratings.

Can this problem be solved with a dynamic programming approach?

While dynamic programming could solve this problem, the greedy approach is more optimal in terms of both time and space complexity.

What are the time and space complexities for the Candy problem?

The time complexity is O(n), and the space complexity is O(n), where n is the number of children in the ratings array.

What is the key invariant used in the Candy problem?

The key invariant is that a child with a higher rating than their neighbors must receive more candies, and the greedy approach ensures this is respected in two passes.

terminal

Solution

Solution 1: Two traversals

We initialize two arrays $left$ and $right$, where $left[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 $right[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, $left[i]=1$, $right[i]=1$.

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        left = [1] * n
        right = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right[i] = right[i + 1] + 1
        return sum(max(a, b) for a, b in zip(left, right))

Continue Practicing

#134 gas station #122 best time to buy and sell stock ii #179 largest number