Candy

Time: O(n)

Space: O(n)

Intuition

Distribute minimum candies so each child gets at least 1 and children with higher rating than neighbor get more. Two-pass greedy.

Algorithm

1Left pass: if ratings[i] > ratings[i-1]: candies[i] = candies[i-1]+1. Else: candies[i]=1.
2Right pass: if ratings[i] > ratings[i+1]: candies[i] = max(candies[i], candies[i+1]+1).

Common Pitfalls

•Same as LC 135. Two passes (left-to-right then right-to-left). Answer = sum of candies array.

Candy.java

Java

// Approach: Two-pass greedy. Left-to-right: give more candy if rating > left neighbor.
// Right-to-left: ensure right neighbor has more if rating > right neighbor. Sum all.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public int minCandy(int arr[]) {
        int n = arr.length;

        int left[] = new int[n];
        int right[] = new int[n];

        Arrays.fill(left, 1);
        Arrays.fill(right, 1);

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > arr[i - 1])
                left[i] += left[i - 1];
        }

        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1])
                right[i] += right[i + 1];
        }

        int maxCandies = 0;

        for (int i = 0; i < left.length; i++)
            maxCandies += Math.max(left[i], right[i]);

        return maxCandies;
    }
}

Was this solution helpful?