LeetCode-135-Candy-proof

https://leetcode.com/problems/candy/description/?envType=study-plan-v2&envId=top-interview-150

14. Candy
Distribute candies to n children such that every child gets \ge 1 candy, and children with higher ratings get more than their immediate neighbors. Minimize the total candies.

Greedy, Array, Two-Pass. O(N) TC.
Key insight: The "neighbors" constraint is bidirectional (left and right). We can decouple this into two unidirectional constraints:
1. Left Pass: Ensure child i has more than i-1 if ratings[i] > ratings[i-1].
2. Right Pass: Ensure child i has more than i+1 if ratings[i] > ratings[i+1].
Algorithm: The minimum candy for any child is the maximum of the requirements imposed by the Left Pass and the Right Pass. Candy[i] = \max(Left[i], Right[i]).

Version 1: Standard Approach (Two Arrays)

Easier to understand. We explicitly build L and R arrays and merge them.

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        L = [1] * n
        R = [1] * n
        
        # 1. Left Pass: Compute constraints from the left neighbor
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                L[i] = L[i-1] + 1
        
        # 2. Right Pass: Compute constraints from the right neighbor
        for i in range(n-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                R[i] = R[i+1] + 1
                
        # 3. Merge: Take the max to satisfy both constraints
        total = 0
        for i in range(n):
            total += max(L[i], R[i])
            
        return total

Version 2: Space Optimized (One Array)

We reuse the candy array from the Left Pass. When doing the Right Pass, we update values in-place using max.

Crucial Logic: Why doesn't the Left Pass data pollute the Right Pass calculation?

• We update candy[i-1] using candy[i] ONLY if ratings[i-1] > ratings[i].
• If ratings[i-1] > ratings[i], it implies ratings[i] < ratings[i-1].
• This means during the first pass (Left Pass), candy[i] did not accumulate a value from i-1. It was reset to (or stayed at) 1 (or its local minimum).
• Therefore, candy[i] does not contain "Left Logic" noise when we need it for the "Right Logic" calculation.

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candy = [1] * n

        # 1. Left Pass: Standard accumulation
        # candy[i] now represents "Left Slope Height"
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                candy[i] = candy[i-1] + 1
        
        # 2. Right Pass: In-place update
        # We process from right to left (n-1 -> 0)
        for i in range(n-1, 0, -1):
            if ratings[i-1] > ratings[i]:
                # LOGIC CHECK:
                # We need to ensure candy[i-1] is higher than candy[i].
                # candy[i] here is safe to use. Since ratings[i] < ratings[i-1], 
                # candy[i] did NOT gain value from candy[i-1] during the Left Pass.
                # We take max() to preserve the Left Pass result if it was already higher.
                candy[i-1] = max(candy[i-1], candy[i] + 1)
        
        return sum(candy)

Proof of Correctness

The Algorithm:

1. Left Pass (L): L_i = L_{i-1} + 1 if r_i > r_{i-1}, else 1.
2. Right Pass (R): R_i = R_{i+1} + 1 if r_i > r_{i+1}, else 1.
3. Result (C): C_i = \max(L_i, R_i).

1. Feasibility (Why it works)

Goal: Prove the solution satisfies the condition "High rating gets more candy".

• Logic:
  • If r_i > r_{i-1} (Left Neighbor Constraint):
    • By definition, L_i = L_{i-1} + 1.
    • Since our result C_i \ge L_i, we guarantee C_i > L_{i-1}.
    • Crucially, at index i-1, the Right Constraint is locally inactive (reset/broken) relative to i, making C_{i-1} effectively bounded by L_{i-1}.
    • Result: C_i > C_{i-1}.
  • Symmetric logic applies for the Right Neighbor (r_i > r_{i+1}).

2. Optimality (Why it's minimal)

Goal: Prove no other valid solution X has a lower sum than C.

• The Inductive Lower Bound:
  Let X be any valid distribution.

  • Left Bound: If r_i > r_{i-1}, then X_i must be \ge X_{i-1} + 1. By induction, this forces X_i \ge L_i for all i.
  • Right Bound: If r_i > r_{i+1}, then X_i must be \ge X_{i+1} + 1. By symmetric induction, this forces X_i \ge R_i for all i.

• The Intersection:
  Since any valid X_i must satisfy both lower bounds simultaneously:
  X_i \ge L_i \quad \text{AND} \quad X_i \ge R_i
  \therefore X_i \ge \max(L_i, R_i)

• Conclusion:
  Since our algorithm sets C_i = \max(L_i, R_i), our solution sits exactly on the tightest possible mathematical lower bound.

Key Intuition (The "One-Liner")

The number of candies required at any position i is determined solely by the length of the longest monotonic slope (chain of increasing ratings) ending at i, either from the left or the right. Taking the max satisfies both slopes simultaneously without over-counting.