L12. Candy | Slope Approach Intuition Based

1. Problem Statement & Core Rules

You are given an array of integers representing the rating values of N children. Your task is to distribute candies to every child satisfying two strict constraints while minimizing the total number of candies distributed:

1. Rule 1 (Bare Minimum): Every child must receive at least 1 candy.
2. Rule 2 (Relative Advantage): Any child with a higher rating than their neighbor must receive strictly more candies than that neighbor. This applies to both left and right neighbors.

Real-Life Analogy: The Escalator Line

Imagine an erratic line of people standing on a staircase of varying heights. If you are standing on a step higher than the person right next to you, protocol demands you must receive a slightly larger reward than them. However, because budget is tight, you want to give out the absolute smallest possible increment that still honors the rules.

2. The Naive Brute-Force Approach (Left & Right Arrays)

To satisfy both left and right neighbor constraints simultaneously, the most direct approach is to break the problem into two independent passes:

1. Left Pass: Iterate from left to right, ensuring every child with a higher rating than their left neighbor gets one more candy than them. If not higher, reset to 1.
2. Right Pass: Iterate from right to left, ensuring every child with a higher rating than their right neighbor gets one more candy than them. If not higher, reset to 1.
3. Merging: For every index i, take the maximum requirement from both passes: max(left[i], right[i]).

Conceptual Left-Right Separation Flow

3. Step-by-Step Optimization: Removing the Right Array

To optimize space, we can eliminate the right array by computing the right-neighbor constraints on the fly during our backward traversal, combining it with a running current candy tracker.

Code Evolution: On-The-Fly Right Pass

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        left[0] = 1;
        
        // Step 1: Compute left neighbor rules
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }
        
        // Step 2: Compute right rules on the fly & accumulate sum
        int sum = Math.max(1, left[n - 1]);
        int current = 1;
        
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                current++;
            } else {
                current = 1;
            }
            sum += Math.max(left[i], current);
        }
        
        return sum;
    }
}

• Complexity Analysis:
  • Time Complexity: $\mathcal{O}(2N)$ — Two passes over the array.
  • Space Complexity: $\mathcal{O}(N)$ — Still requires the left array. To achieve $\mathcal{O}(1)$ space, we need the Slope Approach.

4. The Optimal Slope Approach (Constant Space $\mathcal{O}(1)$)

The interviewer will expect an $\mathcal{O}(1)$ space solution. This is solved by analyzing the rating array as a continuous geometric slope (increasing sequences, decreasing sequences, and flat plateaus).

Mental Model: Climbing Hills and Valleys

Instead of storing full arrays, we traverse the ratings graph:

1. Increasing Slope: Ratings go up. Each step up requires 1 more candy than the previous (1, 2, 3, 4...).
2. Flat Plateaus: Ratings remain equal. Each gets a baseline of 1 candy.
3. Decreasing Slope: Ratings go down. We can similarly count down-slopes starting from 1 (1, 2, 3...), but when a down-slope meets an up-slope at a Peak, the peak must be tall enough to satisfy both sides.

5. Complete Algorithm Walkthrough

Let's break down how the optimal slope tracker operates step-by-step:

Ratings: [0, 2, 4, 7, 6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 2, 1, 0]

1. Handle Flat Plateaus: If ratings[i] == ratings[i - 1], add 1 to the sum and continue.
2. Process Increasing Slope:
   • While ratings increase, increment the peak height, add peak to total sum, and advance index.
3. Process Decreasing Slope:
   • While ratings decrease, increment a down counter starting from 1, add down to total sum, and advance index.
4. Peak Correction:
   • If the down slope length is greater than or equal to the peak height, we must add the extra deficit (down - peak) to our sum because the peak needs to be strictly higher than the highest point of the falling slope.

6. Complete Production-Ready Java Implementation

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        if (n == 0) return 0;
        
        int sum = 1; // First child gets 1 candy minimum
        int i = 1;
        
        while (i < n) {
            // Case 1: Flat surface (Equal ratings)
            if (ratings[i] == ratings[i - 1]) {
                sum += 1;
                i++;
                continue;
            }
            
            // Case 2: Increasing Slope
            int peak = 1;
            while (i < n && ratings[i] > ratings[i - 1]) {
                peak++;
                sum += peak;
                i++;
            }
            
            // Case 3: Decreasing Slope
            int down = 0;
            while (i < n && ratings[i] < ratings[i - 1]) {
                down++;
                sum += down;
                i++;
            }
            
            // Peak Correction: If down slope is taller/equal to peak, 
            // adjust the peak by adding the difference.
            if (down >= peak) {
                sum += (down - peak + 1);
            }
        }
        
        return sum;
    }
}

7. Comparative Strategy Synthesis

8. Summary and Key Takeaways

• Problem Definition: Distribute minimum candies such that every child has $\ge 1$ candy, and higher-rated children get strictly more than neighbors.
• Dual-Constraint Nature: Satisfying both left and right neighbors simultaneously requires evaluating directions independently or utilizing a geometric perspective.
• Space Optimization Journey: Moving from two auxiliary arrays (left and right) down to a single array, and finally eliminating extra storage entirely using the Slope Method.
• Slope Mechanics: Break arrays into structural components: Increasing Hills, Decreasing Valleys, and Flat Plateaus.
• Peak Correction Rule: When a descending slope meets an ascending slope, ensure the shared peak is tall enough to satisfy the downward slope's greatest depth (down >= peak adjustment).
• Complexity Triumph: The slope approach achieves a pristine $\mathcal{O}(N)$ time complexity by traversing every element at most once across nested loops, with $\mathcal{O}(1)$ auxiliary space.