The O(n) Club: Candy: Because Satisfying Kids—and Your Interviewer—Takes Two Passes

The O(n) Club: Candy: Because Satisfying Kids—and Your Interviewer—Takes Two Passes

⚡ TL;DR

LeetCode 135, aka the “Why kids riot over candy” problem: Each child gets at least one candy, but anyone whose rating beats a neighbor needs more. Brute force? Oh please. Two greedy passes—one left, one right—gets it done in O(n) time. Java cheat sheet:

// You only need two sweeps—no, not from the janitor
int[] candies = new int[ratings.length];
Arrays.fill(candies, 1);
for (int i = 1; i < ratings.length; i++)
    if (ratings[i] > ratings[i-1])
        candies[i] = candies[i-1] + 1;
for (int i = ratings.length - 2; i >= 0; i--)
    if (ratings[i] > ratings[i+1])
        candies[i] = Math.max(candies[i], candies[i+1] + 1);
int total = Arrays.stream(candies).sum();

🧠 How Devs Usually Mess This Up

Common misfires: charging in with a single left-to-right pass (sorry, but valleys and late peaks don’t fix themselves). Or handing out equal candies to equal ratings just because it feels “fair”—which isn’t required and only wastes treats. Oh, and the classic: thinking “more kids means more candy”, when it’s really about who showing off next to whom. If your solution feels too easy, you probably missed a test case, and possibly your dignity.

🔍 What’s Actually Going On

Picture a row of kids, snacks on the brain, each eyeing up their competition. The rules: No one gets left behind (everyone gets at least one), but if you outshine your neighbor, you better have more sugar than them. If you only look left, you miss showoffs on the right. That’s why we go twice: once left-to-right to spot the humble overachievers, and once right-to-left for the sneak-attacks at the tail. The magic lies in maxing each kid’s “best so far” as we go back. Two scans ensures no peaks or valleys slip through the cracks. Drama minimized. Headache avoided.

🛠️ PseudoCode

• Step 1: Give everyone 1 candy. (Nobody flips a desk yet.)
  int[] candies = new int[n]; Arrays.fill(candies, 1);
• Step 2: Left to right: If this rating is higher than the kid before, they get one more.
  if (ratings[i] > ratings[i-1]) candies[i] = candies[i-1] + 1;
• Step 3: Right to left: If this rating is higher than the next kid, max current and “next kid’s candies + 1”.
  if (ratings[i] > ratings[i+1]) candies[i] = Math.max(candies[i], candies[i+1] + 1);
• Step 4: Add ’em up and hope there’s no dental bill.
  int total = Arrays.stream(candies).sum();

💻 The Code

public int candy(int[] ratings) {
    int n = ratings.length;
    int[] candies = new int[n];
    Arrays.fill(candies, 1);
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    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 total = 0;
    for (int c : candies) total += c;
    return total;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Single pass = single regret (missed peaks and valleys false negatives).
• Equal ratings? Doesn’t mean equal candies. The rule police won’t bust you.
• If you’re optimizing memory, know you can do this with a little pointer juggling, but basic O(n) space keeps both your code and interviewer calm.
• Time: O(n), space: O(n) with an honest array. No sneaky tricks unless you brag about micro-optimizations on your resume.

🧠 Interviewer Brain-Tattoo

“Two-pass problems: because the universe sometimes needs you to go back and fix your first attempt—just like code reviews.”