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
- A single pass cannot satisfy both directions, so use two passes.
- Left to right: if
ratings[i] > ratings[i-1], setcandies[i] = candies[i-1] + 1. - Right to left: if
ratings[i] > ratings[i+1], setcandies[i] = max(candies[i], candies[i+1] + 1). - 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] + 1can 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.