135. Candy - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement:

There are ( n ) children standing in a line, each with a rating value given by an array ratings. You need to distribute candies to these children subject to the following requirements:

Each child must receive at least one candy.
A child with a higher rating than an adjacent child must receive more candies than that child.

Your goal is to determine the minimum number of candies you must give to distribute according to these rules.

Example Inputs and Outputs:

Example 1:
- Input: ratings = [1, 0, 2]
- Output: 5
- Explanation:
  - Give 2 candies to the first child (rating 1) because it has a higher rating than the second child (rating 0).
  - Give 1 candy to the second child.
  - Give 2 candies to the third child (rating 2) because it has a higher rating than the second child.
  - Total candies = 2 + 1 + 2 = 5.
Example 2:
- Input: ratings = [1, 2, 2]
- Output: 4
- Explanation:
  - Give 1 candy to the first child.
  - Give 2 candies to the second child (since (2 > 1)).
  - The third child has the same rating as the second child, so it only needs 1 candy.
  - However, to satisfy the rule for the second child, we must ensure the second child has strictly more than its lower-rated neighbor. Since the third child doesn’t require more (they are equal), we can assign 1 candy to the third.
  - Total candies = 1 + 2 + 1 = 4.

Constraints:

$( 1 \leq \text{ratings.length} \leq 2 \times 10^4 )$
$( 0 \leq \text{ratings}[i] \leq 2 \times 10^4 )$

Hints for Solving the Problem:

Greedy Two-Pass Approach:
- One intuitive way is to scan from left to right ensuring that each child with a higher rating than the previous gets one more candy.
- Then, scan from right to left to correct any cases where a child on the left might have a higher rating than its right neighbor but wasn’t given enough candies.
Maintaining Local Conditions:
- Make sure every child satisfies the condition with respect to both the left and right neighbors.

Optimal Approach: Two-Pass Greedy Method

Step-by-Step Explanation:

Initialization:
- Create an array candies of the same length as ratings and initialize every element to 1 because each child must get at least one candy.
Left-to-Right Pass:
- Traverse the array from left to right.
- For each child ( i ) (starting from index 1), if $( \text{ratings}[i] > \text{ratings}[i-1] )$ , then update: $[ \text{candies}[i] = \text{candies}[i-1] + 1 ]$
- This ensures that a child with a higher rating than its left neighbor gets more candies.
Right-to-Left Pass:
- Traverse the array from right to left.
- For each child ( i ) (starting from the second last index), if $( \text{ratings}[i] > \text{ratings}[i+1] )$ , then update: $[ \text{candies}[i] = \max(\text{candies}[i], \text{candies}[i+1] + 1) ]$
- This pass ensures that a child with a higher rating than its right neighbor also receives more candies.
Final Answer:
- Sum up the values in the candies array to get the minimum number of candies needed.

Why It Works:

The left-to-right pass guarantees the condition for the left neighbor.
The right-to-left pass ensures the condition for the right neighbor.
Using the maximum during the second pass guarantees that both conditions are met without reducing any previously assigned candies.

Python Code:

Python3

. . . .

Java Code:

Java

. . . .

Complexity Analysis:

Time Complexity:
- Two passes through the array (left-to-right and right-to-left), so overall ( O(n) ).
Space Complexity:
- ( O(n) ) for the candies array.

Edge Cases:

All Children with Same Rating:
- Each child will get exactly 1 candy.
Strictly Increasing or Decreasing Ratings:
- For strictly increasing ratings, the candies array will be $([1, 2, 3, \dots])$ .
- For strictly decreasing ratings, the candies array will be reversed accordingly.
Single Child:
- When there is only one child, the answer is 1.

Common Mistakes:

Not Handling Both Directions:
- Focusing only on the left-to-right pass might satisfy one condition but can miss the requirement when comparing with the right neighbor.
Using Incorrect Update Logic:
- Forgetting to use the maximum during the right-to-left pass might override a correct candy count from the left-to-right pass.
Edge Case Overlook:
- Not handling cases where ratings are equal (children with the same rating don’t require a higher candy count).

Related Problems for Further Practice:

Candy Crush (Grid-based simulation) [Different problem theme]
Task Scheduler (LeetCode 621):
- Involves scheduling with greedy algorithms.
Longest Increasing Subsequence (LeetCode 300):
- Although not the same problem, it involves processing sequences with increasing properties.