⚡Flashcard Drill➔
NeetCode #804LC-135HardGreedyNC 250
← Back to All Problems

#804 · #135 · Candy(分发糖果)

📌 Problem Statement & Constraints

There are n children in a line, each with a ratings[i]. Give each child at least one candy; any child with a higher rating than an immediate neighbour must receive more candies than that neighbour. Return the minimum total candies. Constraints: 1 <= n <= 2 * 10^4, 0 <= ratings[i] <= 2 * 10^4.

💡 Core Algorithmic Approaches

  1. A single pass cannot satisfy both directions, so use two passes.
  2. Left to right: if ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1.
  3. Right to left: if ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1).
  4. Taking the maximum in the second pass preserves the constraints already satisfied by the first.

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): two linear passes.
💾 Space Complexity
O(n): the candy array.

⚠️ Interview Pitfalls & Follow-ups

  • Using a single pass: it cannot satisfy both the left and right constraints simultaneously.
  • Overwriting in the second pass instead of taking the maximum: candies[i] = candies[i+1] + 1 can violate the left-neighbour rule.
  • Requiring strictly more candies for equal ratings: equal ratings impose no constraint, so both may keep the same count.
  • Assuming the peak child gets the sum of both slopes: the correct value is the maximum of the two directional needs, not their sum.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems