LeetCode 135: Candy Solution in Python Explained

Problem Statement

In LeetCode 135, you’re given an integer array ratings of length n, where ratings[i] is the rating of the i-th child in a line. Your task is to return the minimum number of candies to distribute, following these rules: 1. Each child gets at least 1 candy. 2. If a child’s rating is higher than their neighbor’s, they must get more candies than that neighbor.

This differs from circular traversal like LeetCode 134: Gas Station, focusing on a linear array with local comparisons rather than a circuit.

Constraints

• 1 <= ratings.length <= 2 * 10^4
• 0 <= ratings[i] <= 2 * 10^4

Example

Let’s see some cases:

Copy codeInput: ratings = [1,0,2]
Output: 5
Explanation: Candies: [2,1,2]
<ul>
<li>Child 0 (1) > Child 1 (0), gets 2.</li>
<li>Child 1 (0), minimum 1.</li>
<li>Child 2 (2) > Child 1 (0), gets 2.</li>
<li>Total: 2+1+2 = 5.</li>
</ul>

Copy codeInput: ratings = [1,2,2]
Output: 4
Explanation: Candies: [1,2,1]
<ul>
<li>Child 0 (1) < Child 1 (2), gets 1.</li>
<li>Child 1 (2), gets 2 (more than 0).</li>
<li>Child 2 (2) = Child 1 (2), gets 1 (minimum).</li>
<li>Total: 1+2+1 = 4.</li>
</ul>

Copy codeInput: ratings = [1,3,2,1]
Output: 7
Explanation: Candies: [1,3,2,1]
<ul>
<li>Child 0 (1) < Child 1 (3), gets 1.</li>
<li>Child 1 (3) > Child 0 (1) and Child 2 (2), gets 3.</li>
<li>Child 2 (2) > Child 3 (1), gets 2.</li>
<li>Child 3 (1), gets 1.</li>
<li>Total: 1+3+2+1 = 7.</li>
</ul>

These examples show we’re minimizing candies while satisfying neighbor rules.

Understanding the Problem

How do you solve LeetCode 135: Candy in Python? Take ratings = [1,0,2]. We need the minimum candies: child 0 (rating 1) > child 1 (rating 0), child 2 (rating 2) > child 1 (rating 0), so [2,1,2] gives 5 candies. For [1,2,2], equal ratings allow minimum candies after a peak, so [1,2,1] gives 4. This isn’t a path sum problem like LeetCode 113: Path Sum II; it’s about array-based greedy allocation. We’ll use: 1. Two-Pass Greedy: O(n) time, O(n) space—our best solution. 2. Single-Pass with Peaks and Valleys: O(n) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Two-Pass Greedy Approach

Explanation

Two-Pass Greedy assigns candies in two sweeps: a left-to-right pass ensures each child gets more than their left neighbor if their rating is higher, and a right-to-left pass adjusts for right neighbors, taking the maximum from both passes. This is the best solution due to its O(n) time complexity, clear logic ensuring all conditions are met, and straightforward implementation, making it reliable and easy to understand.

For [1,0,2]:

• Left pass: [1,1,2] (2 > 0).
• Right pass: [2,1,2] (1 > 0, 2 > 1 adjusted left).
• Total: 5.

Step-by-Step Example

Example 1: ratings = [1,0,2]

Goal: Return 5.

• Start: candies = [1,1,1], n = 3.
• Left Pass:
• i=1: 0 < 1, candies[1] = 1.
• i=2: 2 > 0, candies[2] = 1+1 = 2.
• candies = [1,1,2].
• Right Pass:
• i=1: 0 < 2, candies[1] = 1.
• i=0: 1 > 0, candies[0] = max(1, 1+1) = 2.
• candies = [2,1,2].
• Sum: 2+1+2 = 5.
• Finish: Return 5.

Example 2: ratings = [1,2,2]

Goal: Return 4.

• Start: candies = [1,1,1].
• Left Pass:
• i=1: 2 > 1, candies[1] = 2.
• i=2: 2 = 2, candies[2] = 1.
• candies = [1,2,1].
• Right Pass:
• i=1: 2 = 2, candies[1] = 2.
• i=0: 1 < 2, candies[0] = 1.
• candies = [1,2,1].
• Sum: 1+2+1 = 4.
• Finish: Return 4.

Example 3: ratings = [1,3,2,1]

Goal: Return 7.

• Start: candies = [1,1,1,1].
• Left Pass:
• i=1: 3 > 1, candies[1] = 2.
• i=2: 2 < 3, candies[2] = 1.
• i=3: 1 < 2, candies[3] = 1.
• candies = [1,2,1,1].
• Right Pass:
• i=2: 2 > 1, candies[2] = max(1, 1+1) = 2.
• i=1: 3 > 2, candies[1] = max(2, 2+1) = 3.
• i=0: 1 < 3, candies[0] = 1.
• candies = [1,3,2,1].
• Sum: 1+3+2+1 = 7.
• Finish: Return 7.

How the Code Works (Two-Pass Greedy) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef candy(ratings: list[int]) -> int:
    # Line 1: Get number of children
    n = len(ratings)
    # Length of ratings array (e.g., 3 for [1,0,2])

    # Line 2: Initialize candies array with minimum 1
    candies = [1] * n
    # Each child starts with 1 candy (e.g., [1,1,1])

    # Line 3: Left-to-right pass
    for i in range(1, n):
        # i = 1 to n-1 (e.g., 1 to 2)

        # Line 4: Check if current rating > previous
        if ratings[i] > ratings[i-1]:
            # If higher (e.g., 2 > 0), give more than left neighbor
            candies[i] = candies[i-1] + 1
            # e.g., candies[2] = 1+1 = 2

    # Line 5: Right-to-left pass
    for i in range(n-2, -1, -1):
        # i = n-2 to 0 (e.g., 1 to 0)

        # Line 6: Check if current rating > next
        if ratings[i] > ratings[i+1]:
            # If higher (e.g., 1 > 0), ensure more than right neighbor
            candies[i] = max(candies[i], candies[i+1] + 1)
            # e.g., candies[0] = max(1, 1+1) = 2
            # Max ensures left pass isn’t overridden unless needed

    # Line 7: Return total candies
    return sum(candies)
    # Sums array (e.g., [2,1,2] → 5)

This detailed breakdown clarifies how the two-pass greedy approach efficiently assigns candies.

Alternative: Single-Pass with Peaks and Valleys Approach

Explanation

Single-Pass with Peaks and Valleys scans the array once, counting candies by identifying peaks (local maxima) and valleys (local minima), calculating contributions based on increasing/decreasing sequences. It’s a clever alternative, achieving O(n) time with O(1) space, but it’s more complex to implement and understand.

For [1,0,2]:

• Up: 1 (1->0), Down: 1+1 (0->2), Peak: 2-1=1, Total: 1+2=3+2=5.

Step-by-Step Example (Alternative)

For [1,0,2]:

• Start: candies = 0, prev = 1.
• Step 1: i=1, 0 < 1, down = 1, candies = 1.
• Step 2: i=2, 2 > 0, up = 1, peak = max(1,1)-1=0, candies = 1+1+2=4+1=5.
• Finish: Return 5.

How the Code Works (Peaks and Valleys)

Copy codedef candyPeaksValleys(ratings: list[int]) -> int:
    if not ratings:
        return 0
    n = len(ratings)
    if n == 1:
        return 1
    candies = up = down = 0
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            up += 1
            down = 0
            candies += up + max(up, down) - (1 if up > down else 0)
        elif ratings[i] < ratings[i-1]:
            down += 1
            up = 0
            candies += down + max(up, down) - (1 if up > down else 0)
        else:
            up = down = 0
            candies += 1
    return candies + 1  # Add base candy for first child

Complexity

• Two-Pass Greedy:
• Time: O(n) – two linear passes.
• Space: O(n) – candies array.
• Single-Pass with Peaks and Valleys:
• Time: O(n) – single pass.
• Space: O(1) – constant space.

Efficiency Notes

Two-Pass Greedy is the best solution with O(n) time and O(n) space, offering clarity and reliability—Single-Pass with Peaks and Valleys matches time complexity with O(1) space, but its complexity makes it less intuitive, though more space-efficient.

Key Insights

• Greedy: Local comparisons suffice.
• Two-Pass: Ensures all conditions.
• Peaks: Handles slopes efficiently.

Additional Example

For ratings = [1,2,3,2]:

• Goal: 7.
• Two-Pass: [1,2,3,1], total 7.

Edge Cases

• Single Child: [1] → 1.
• All Equal: [1,1,1] → 3.
• Decreasing: [3,2,1] → 6.

Both solutions handle these well.

Final Thoughts

LeetCode 135: Candy in Python is a delightful greedy challenge. The Two-Pass Greedy solution excels with its efficiency and simplicity, while Single-Pass with Peaks and Valleys offers a space-optimized twist. Want more? Try LeetCode 134: Gas Station for another greedy problem or LeetCode 94: Binary Tree Inorder Traversal for tree basics. Ready to practice? Solve LeetCode 135 on LeetCode with [1,0,2], aiming for 5—test your skills now!