135. Candy - Explanation

Description

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [4,3,5]

Output: 5

Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [2,3,3]

Output: 4

Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

1 <= ratings.length <= 20,000
0 <= ratings[i] <= 20,000

Topics

Array Greedy

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Traversing and modifying arrays in both directions
Greedy Algorithms - Making locally optimal choices to achieve a global optimum
Two-Pass Technique - Processing data in multiple passes to satisfy multiple constraints

1. Brute Force

Intuition

We process children left to right, adjusting candies to satisfy the constraint that higher-rated children get more candy than their neighbors. When we increase a child's candy count, we may violate the constraint with a previous child, so we propagate updates backward as needed. This approach ensures correctness but may revisit the same positions multiple times.

Algorithm

Initialize an array where each child starts with 1 candy.
Iterate through adjacent pairs from left to right.
If the current child has a higher rating than the previous one, give them one more candy than the previous child.
If the current child has a lower rating and they have the same number of candies, increment the previous child's candy count and propagate backward: for each earlier child with a higher rating than their right neighbor, increase their candy if needed.
Return the sum of all candies.

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

        for i in range(n - 1):
            if ratings[i] == ratings[i + 1]:
                continue
            if ratings[i + 1] > ratings[i]:
                arr[i + 1] = arr[i] + 1
            elif arr[i] == arr[i + 1]:
                arr[i + 1] = arr[i]
                arr[i] += 1
                for j in range(i - 1, -1, -1):
                    if ratings[j] > ratings[j + 1]:
                        if arr[j + 1] < arr[j]:
                            break
                        arr[j] += 1

        return sum(arr)

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = 1;
        }

        for (int i = 0; i < n - 1; i++) {
            if (ratings[i] == ratings[i + 1]) {
                continue;
            }
            if (ratings[i + 1] > ratings[i]) {
                arr[i + 1] = arr[i] + 1;
            } else if (arr[i] == arr[i + 1]) {
                arr[i + 1] = arr[i];
                arr[i]++;
                for (int j = i - 1; j >= 0; j--) {
                    if (ratings[j] > ratings[j + 1]) {
                        if (arr[j + 1] < arr[j]) {
                            break;
                        }
                        arr[j]++;
                    }
                }
            }
        }

        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        return sum;
    }
}

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> arr(n, 1);

        for (int i = 0; i < n - 1; i++) {
            if (ratings[i] == ratings[i + 1]) {
                continue;
            }
            if (ratings[i + 1] > ratings[i]) {
                arr[i + 1] = arr[i] + 1;
            } else if (arr[i] == arr[i + 1]) {
                arr[i + 1] = arr[i];
                arr[i]++;
                for (int j = i - 1; j >= 0; j--) {
                    if (ratings[j] > ratings[j + 1]) {
                        if (arr[j + 1] < arr[j]) {
                            break;
                        }
                        arr[j]++;
                    }
                }
            }
        }

        return accumulate(arr.begin(), arr.end(), 0);
    }
};

class Solution {
    /**
     * @param {number[]} ratings
     * @return {number}
     */
    candy(ratings) {
        const n = ratings.length;
        const arr = new Array(n).fill(1);

        for (let i = 0; i < n - 1; i++) {
            if (ratings[i] === ratings[i + 1]) {
                continue;
            }
            if (ratings[i + 1] > ratings[i]) {
                arr[i + 1] = arr[i] + 1;
            } else if (arr[i] === arr[i + 1]) {
                arr[i + 1] = arr[i];
                arr[i]++;
                for (let j = i - 1; j >= 0; j--) {
                    if (ratings[j] > ratings[j + 1]) {
                        if (arr[j + 1] < arr[j]) {
                            break;
                        }
                        arr[j]++;
                    }
                }
            }
        }

        return arr.reduce((sum, num) => sum + num, 0);
    }
}

public class Solution {
    public int Candy(int[] ratings) {
        int n = ratings.Length;
        int[] arr = new int[n];
        Array.Fill(arr, 1);

        for (int i = 0; i < n - 1; i++) {
            if (ratings[i] == ratings[i + 1]) {
                continue;
            }
            if (ratings[i + 1] > ratings[i]) {
                arr[i + 1] = arr[i] + 1;
            } else if (arr[i] == arr[i + 1]) {
                arr[i + 1] = arr[i];
                arr[i]++;
                for (int j = i - 1; j >= 0; j--) {
                    if (ratings[j] > ratings[j + 1]) {
                        if (arr[j + 1] < arr[j]) break;
                        arr[j]++;
                    } else {
                        break;
                    }
                }
            }
        }

        int total = 0;
        foreach (int a in arr) {
            total += a;
        }
        return total;
    }
}

class Solution {
    fun candy(ratings: IntArray): Int {
        val n = ratings.size
        val arr = IntArray(n) { 1 }

        for (i in 0 until n - 1) {
            if (ratings[i] == ratings[i + 1]) {
                continue
            }
            if (ratings[i + 1] > ratings[i]) {
                arr[i + 1] = arr[i] + 1
            } else if (arr[i] == arr[i + 1]) {
                arr[i + 1] = arr[i]
                arr[i]++
                for (j in i - 1 downTo 0) {
                    if (ratings[j] > ratings[j + 1]) {
                        if (arr[j + 1] < arr[j]) break
                        arr[j]++
                    } else {
                        break
                    }
                }
            }
        }

        return arr.sum()
    }
}

class Solution {
    func candy(_ ratings: [Int]) -> Int {
        let n = ratings.count
        var arr = [Int](repeating: 1, count: n)

        for i in 0..<(n - 1) {
            if ratings[i] == ratings[i + 1] {
                continue
            }
            if ratings[i + 1] > ratings[i] {
                arr[i + 1] = arr[i] + 1
            } else if arr[i] == arr[i + 1] {
                arr[i + 1] = arr[i]
                arr[i] += 1
                for j in stride(from: i - 1, through: 0, by: -1) {
                    if ratings[j] > ratings[j + 1] {
                        if arr[j + 1] < arr[j] { break }
                        arr[j] += 1
                    } else {
                        break
                    }
                }
            }
        }

        return arr.reduce(0, +)
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Greedy (Two Pass)

Intuition

We can handle left and right neighbors separately. First, scan left to right to ensure each child with a higher rating than their left neighbor gets more candy. Then, scan right to left to handle the right neighbor constraint. When adjusting for right neighbors, we take the maximum of the current value and what the right constraint requires, preserving the left constraint satisfaction.

Algorithm

Initialize an array where each child starts with 1 candy.
First pass (left to right): if a child's rating is higher than their left neighbor's, set their candy count to one more than the left neighbor.
Second pass (right to left): if a child's rating is higher than their right neighbor's, set their candy count to the maximum of its current value and one more than the right neighbor.
Return the sum of all candies.

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

        for i in range(1, n):
            if ratings[i - 1] < ratings[i]:
                arr[i] = arr[i - 1] + 1

        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                arr[i] = max(arr[i], arr[i + 1] + 1)

        return sum(arr)

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

        for (int i = 1; i < n; i++) {
            if (ratings[i - 1] < ratings[i]) {
                arr[i] = arr[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                arr[i] = Math.max(arr[i], arr[i + 1] + 1);
            }
        }

        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        return sum;
    }
}

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> arr(n, 1);

        for (int i = 1; i < n; i++) {
            if (ratings[i - 1] < ratings[i]) {
                arr[i] = arr[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                arr[i] = max(arr[i], arr[i + 1] + 1);
            }
        }

        return accumulate(arr.begin(), arr.end(), 0);
    }
};

class Solution {
    /**
     * @param {number[]} ratings
     * @return {number}
     */
    candy(ratings) {
        const n = ratings.length;
        const arr = new Array(n).fill(1);

        for (let i = 1; i < n; i++) {
            if (ratings[i - 1] < ratings[i]) {
                arr[i] = arr[i - 1] + 1;
            }
        }

        for (let i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                arr[i] = Math.max(arr[i], arr[i + 1] + 1);
            }
        }

        return arr.reduce((sum, num) => sum + num, 0);
    }
}

public class Solution {
    public int Candy(int[] ratings) {
        int n = ratings.Length;
        int[] arr = new int[n];
        Array.Fill(arr, 1);

        for (int i = 1; i < n; i++) {
            if (ratings[i - 1] < ratings[i]) {
                arr[i] = arr[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                arr[i] = Math.Max(arr[i], arr[i + 1] + 1);
            }
        }

        int total = 0;
        foreach (int a in arr) {
            total += a;
        }
        return total;
    }
}

class Solution {
    fun candy(ratings: IntArray): Int {
        val n = ratings.size
        val arr = IntArray(n) { 1 }

        for (i in 1 until n) {
            if (ratings[i - 1] < ratings[i]) {
                arr[i] = arr[i - 1] + 1
            }
        }

        for (i in n - 2 downTo 0) {
            if (ratings[i] > ratings[i + 1]) {
                arr[i] = maxOf(arr[i], arr[i + 1] + 1)
            }
        }

        return arr.sum()
    }
}

class Solution {
    func candy(_ ratings: [Int]) -> Int {
        let n = ratings.count
        var arr = [Int](repeating: 1, count: n)

        for i in 1..<n {
            if ratings[i - 1] < ratings[i] {
                arr[i] = arr[i - 1] + 1
            }
        }

        for i in stride(from: n - 2, through: 0, by: -1) {
            if ratings[i] > ratings[i + 1] {
                arr[i] = max(arr[i], arr[i + 1] + 1)
            }
        }

        return arr.reduce(0, +)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Greedy (One Pass)

Intuition

We can compute the result without storing candy counts for each child. The key insight is that ratings form a sequence of increasing and decreasing runs. For an increasing run of length k, we need 1+2+...+k extra candies above the base. For a decreasing run of length k, we also need 1+2+...+k extra candies. The peak between an increasing and decreasing run should belong to whichever run is longer.

Algorithm

Start with n candies (one per child as the base).
Iterate through the ratings, skipping equal adjacent ratings.
Count the length of each increasing run (consecutive ratings going up) and add the triangular number sum (1+2+...+inc) to the result.
Count the length of each decreasing run (consecutive ratings going down) and add its triangular sum to the result.
Subtract the minimum of the two run lengths since the peak was counted in both runs but should only be counted once (in the longer run).
Return the total.

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

        i = 1
        while i < n:
            if ratings[i] == ratings[i - 1]:
                i += 1
                continue

            inc = 0
            while i < n and ratings[i] > ratings[i - 1]:
                inc += 1
                res += inc
                i += 1

            dec = 0
            while i < n and ratings[i] < ratings[i - 1]:
                dec += 1
                res += dec
                i += 1

            res -= min(inc, dec)

        return res

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int res = n;

        int i = 1;
        while (i < n) {
            if (ratings[i] == ratings[i - 1]) {
                i++;
                continue;
            }

            int inc = 0;
            while (i < n && ratings[i] > ratings[i - 1]) {
                inc++;
                res += inc;
                i++;
            }

            int dec = 0;
            while (i < n && ratings[i] < ratings[i - 1]) {
                dec++;
                res += dec;
                i++;
            }

            res -= Math.min(inc, dec);
        }

        return res;
    }
}

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        int res = n;

        int i = 1;
        while (i < n) {
            if (ratings[i] == ratings[i - 1]) {
                i++;
                continue;
            }

            int inc = 0;
            while (i < n && ratings[i] > ratings[i - 1]) {
                inc++;
                res += inc;
                i++;
            }

            int dec = 0;
            while (i < n && ratings[i] < ratings[i - 1]) {
                dec++;
                res += dec;
                i++;
            }

            res -= min(inc, dec);
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} ratings
     * @return {number}
     */
    candy(ratings) {
        const n = ratings.length;
        let res = n;

        let i = 1;
        while (i < n) {
            if (ratings[i] === ratings[i - 1]) {
                i++;
                continue;
            }

            let inc = 0;
            while (i < n && ratings[i] > ratings[i - 1]) {
                inc++;
                res += inc;
                i++;
            }

            let dec = 0;
            while (i < n && ratings[i] < ratings[i - 1]) {
                dec++;
                res += dec;
                i++;
            }

            res -= Math.min(inc, dec);
        }

        return res;
    }
}

public class Solution {
    public int Candy(int[] ratings) {
        int n = ratings.Length;
        int res = n;
        int i = 1;

        while (i < n) {
            if (ratings[i] == ratings[i - 1]) {
                i++;
                continue;
            }

            int inc = 0;
            while (i < n && ratings[i] > ratings[i - 1]) {
                inc++;
                res += inc;
                i++;
            }

            int dec = 0;
            while (i < n && ratings[i] < ratings[i - 1]) {
                dec++;
                res += dec;
                i++;
            }

            res -= Math.Min(inc, dec);
        }

        return res;
    }
}

func candy(ratings []int) int {
    n := len(ratings)
    res := n

    i := 1
    for i < n {
        if ratings[i] == ratings[i-1] {
            i++
            continue
        }

        inc := 0
        for i < n && ratings[i] > ratings[i-1] {
            inc++
            res += inc
            i++
        }

        dec := 0
        for i < n && ratings[i] < ratings[i-1] {
            dec++
            res += dec
            i++
        }

        if inc < dec {
            res -= inc
        } else {
            res -= dec
        }
    }

    return res
}

class Solution {
    fun candy(ratings: IntArray): Int {
        val n = ratings.size
        var res = n

        var i = 1
        while (i < n) {
            if (ratings[i] == ratings[i - 1]) {
                i++
                continue
            }

            var inc = 0
            while (i < n && ratings[i] > ratings[i - 1]) {
                inc++
                res += inc
                i++
            }

            var dec = 0
            while (i < n && ratings[i] < ratings[i - 1]) {
                dec++
                res += dec
                i++
            }

            res -= minOf(inc, dec)
        }

        return res
    }
}

class Solution {
    func candy(_ ratings: [Int]) -> Int {
        let n = ratings.count
        var res = n

        var i = 1
        while i < n {
            if ratings[i] == ratings[i - 1] {
                i += 1
                continue
            }

            var inc = 0
            while i < n && ratings[i] > ratings[i - 1] {
                inc += 1
                res += inc
                i += 1
            }

            var dec = 0
            while i < n && ratings[i] < ratings[i - 1] {
                dec += 1
                res += dec
                i += 1
            }

            res -= min(inc, dec)
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Giving Extra Candy for Equal Ratings

Children with equal ratings do not need to have the same or related candy counts. Only strictly higher ratings require more candy than neighbors.

# Wrong: treating equal ratings like higher ratings
if ratings[i] >= ratings[i - 1]:
    arr[i] = arr[i - 1] + 1

Only Considering One Direction

A single left-to-right pass handles the left neighbor constraint but ignores the right neighbor. The two-pass approach ensures both constraints are satisfied.

Not Taking Maximum in Second Pass

In the right-to-left pass, simply setting arr[i] = arr[i + 1] + 1 may violate the left neighbor constraint already established. You must take the maximum of the current value and the right constraint.

# Wrong: overwrites left constraint
arr[i] = arr[i + 1] + 1
# Correct: preserves both constraints
arr[i] = max(arr[i], arr[i + 1] + 1)

Off-by-One in Peak Handling (One-Pass Solution)

When counting increasing and decreasing sequences, the peak element gets counted in both. Forgetting to subtract min(inc, dec) results in overcounting candies.