Leetcode - Candy Solution

Distributing candy to children based on their ratings sounds simple at first - just give more candy to kids with higher ratings. But here's the catch: a child needs to have more candy than both neighbors if they have a higher rating than both. That's when I realized this problem needs a two-pass approach.

The solution processes constraints from both directions: first left-to-right to ensure each child has more candy than their left neighbor if they have a higher rating, then right-to-left to ensure they have more than their right neighbor. The key is using Math.max in the second pass to preserve the work from the first pass.

The Problem

I have n children standing in a queue, each with a rating. I need to distribute candy with these rules:

1. Each child must get at least one candy
2. Children with higher ratings must get more candy than their neighbors

The goal is to find the minimum number of candies needed.

My First Attempt

My initial thought was: "I'll just go through once and give more candy to kids with higher ratings." But I quickly ran into a problem. What if a child has a higher rating than the child on the left, but also higher than the child on the right? I need to satisfy both constraints!

Let me show you what I tried first:

function candyNaive(ratings) {
  const n = ratings.length;
  const candies = new Array(n).fill(1);

  // Only checking left neighbor
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }

  return candies.reduce((a, b) => a + b, 0);
}

This didn't work for cases like [1, 0, 2] because I wasn't checking the right neighbor.

The Two-Pass Insight

I realized I needed to check constraints from both directions. Here's my thought process:

1. First pass (left to right): Make sure each child has more candy than their left neighbor if they have a higher rating
2. Second pass (right to left): Make sure each child has more candy than their right neighbor if they have a higher rating, but don't decrease if they already have more

The key insight was using Math.max in the second pass to preserve the work from the first pass.

My Solution

function candy(ratings) {
  const n = ratings.length;
  const candies = new Array(n).fill(1); // Everyone starts with 1 candy

  // First pass: left to right
  // If current child has higher rating than left neighbor, give more candy
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }

  // Second pass: right to left
  // If current child has higher rating than right neighbor,
  // make sure they have at least one more candy
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      // Use Math.max to preserve what we did in first pass
      candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
  }

  return candies.reduce((a, b) => a + b, 0);
}

// Example usage:
const ratings = [1, 0, 2];
console.log(candy(ratings)); // Output: 5

Let me trace through [1, 0, 2]:

• Initial: [1, 1, 1]
• After first pass: [1, 1, 2] (child 2 has higher rating than child 1)
• After second pass: [2, 1, 2] (child 0 has higher rating than child 1, so needs at least 2)
• Total: 2 + 1 + 2 = 5

Why Math.max Matters

The Math.max in the second pass is crucial. It ensures we don't reduce candies that were already correctly assigned in the first pass. For example, if a child already has 3 candies from the left-to-right pass, and the right-to-left pass suggests 2, we keep 3.

Java Version

public class Candy {
    public static int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);

        // Pass from left to right
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Pass from right to left
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }

        return totalCandies;
    }

    public static void main(String[] args) {
        int[] ratings = {1, 0, 2};
        System.out.println(candy(ratings)); // Output: 5
    }
}

What I Learned

This problem taught me that sometimes you need to look at constraints from multiple directions. The two-pass approach is a common pattern when you have bidirectional constraints. I also learned the importance of using Math.max to preserve previous work when doing multiple passes.

Key Takeaways

• Two-pass algorithms are useful when constraints come from both directions
• Always preserve previous work when doing multiple passes (use Math.max or similar)
• Start with the minimum requirement (everyone gets 1 candy) and build up
• This pattern appears in other problems with bidirectional constraints

I found this problem really satisfying once I understood the two-pass approach. It's a great example of how breaking a problem into steps can make it much clearer!