135. Candy - Solution & Explanation

The problem

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 = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
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:

n == ratings.length
1 <= n <= 2 * 10⁴
0 <= ratings[i] <= 2 * 10⁴

Approach overview

Problem Overview: You receive an array of ratings where each element represents a child's rating. Every child must get at least one candy, and children with a higher rating than their immediate neighbor must receive more candies. The goal is to minimize the total candies distributed while satisfying both constraints.

Approach 1: Two-Pass Solution (Greedy) (Time: O(n), Space: O(n))

This greedy strategy scans the ratings twice to enforce the left and right neighbor constraints independently. Start by allocating one candy to every child using an array candies. In the first pass (left → right), if ratings[i] > ratings[i-1], assign candies[i] = candies[i-1] + 1. This guarantees that higher-rated children on the right get more candies than the left neighbor. The second pass (right → left) fixes the opposite condition: if ratings[i] > ratings[i+1], update candies[i] = max(candies[i], candies[i+1] + 1). Using max preserves assignments from the first pass. Finally, sum the array to get the minimum candies. This method is simple, deterministic, and widely accepted in interviews. It’s a classic Greedy pattern applied on an Array.

Approach 2: Single-Pass with Two Arrays (Time: O(n), Space: O(n))

Another way to model the constraints is to compute two directional requirements explicitly. Maintain two arrays: left[i] represents the candies needed to satisfy the left neighbor rule, and right[i] represents the candies required to satisfy the right neighbor rule. Traverse left → right to populate left: when ratings[i] > ratings[i-1], set left[i] = left[i-1] + 1, otherwise keep it at 1. Then traverse right → left to fill right similarly using the right neighbor comparison. The final candies for each child become max(left[i], right[i]), ensuring both conditions hold simultaneously. Summing these values yields the minimum valid distribution. This approach makes the directional constraints explicit and can be easier to reason about when debugging greedy logic.

Recommended for interviews: The two-pass greedy solution is the expected answer. It demonstrates that you can break the constraint into directional rules and enforce them with linear scans. Explaining the intuition behind the passes shows understanding of greedy algorithms. Mentioning the two-array variation helps show alternative thinking, but the single array two-pass implementation is typically what interviewers want to see.

Approach 1: Two-Pass Solution

The idea behind the Two-Pass Solution is to first ensure each child has more candies than the child before them if their rating is higher, and then make another pass to ensure the condition is also satisfied going from right to left. By leveraging two passes, we ensure that the candy distribution meets the requirements in both directions.

Python

class Solution:
    def candy(self, ratings):
        n = len(ratings)
        candies = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
        return sum(candies)

# Example Usage
sol = Solution()
print(sol.candy([1, 0, 2]))

Java

import java.util.Arrays;

public class CandyDistribution {
    public static 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 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));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> candies(n, 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] = max(candies[i], candies[i + 1] + 1);
        }
    }
    return accumulate(candies.begin(), candies.end(), 0);
}

int main() {
    vector<int> ratings = {1, 0, 2};
    cout << candy(ratings) << endl;
    return 0;
}

JavaScript

function candy(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);
    for (let i = 1; i < n; ++i) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    for (let i = n - 2; i >= 0; --i) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }
    return candies.reduce((sum, a) => sum + a, 0);
}

// Example usage
console.log(candy([1, 0, 2]));

#include <stdio.h>
#include <string.h>

int candy(int* ratings, int ratingsSize) {
    int candies[ratingsSize];
    memset(candies, 0, sizeof(candies));
    for (int i = 0; i < ratingsSize; i++) {
        candies[i] = 1;
    }
    for (int i = 1; i < ratingsSize; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    for (int i = ratingsSize - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = candies[i] > candies[i + 1] + 1 ? candies[i] : candies[i + 1] + 1;
        }
    }
    int totalCandies = 0;
    for (int i = 0; i < ratingsSize; i++) {
        totalCandies += candies[i];
    }
    return totalCandies;
}

int main() {
    int ratings[] = {1, 0, 2};
    int size = sizeof(ratings) / sizeof(ratings[0]);
    printf("%d\n", candy(ratings, size));
    return 0;
}

using System;

public class Solution {
    public int Candy(int[] ratings) {
        int n = ratings.Length;
        int[] candies = new int[n];
        Array.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 totalCandies = 0;
        foreach (int candy in candies) {
            totalCandies += candy;
        }
        return totalCandies;
    }

    static void Main() {
        Solution sol = new Solution();
        int[] ratings = {1, 0, 2};
        Console.WriteLine(sol.Candy(ratings));
    }
}

The Python solution uses list comprehensions to initialize the candies list. It conducts two passes over the `ratings` list to ensure proper candy distribution per the ratings. Finally, the `sum` function is used to calculate the total number of candies needed.

Complexity

Time Complexity: O(n)

Space Complexity: O(n)

Try this approach in the editor

Approach 2: Single-Pass with Two Arrays

This method involves the use of two arrays to maintain the candies given on left-to-right and right-to-left conditions separately. Instead of managing passes sequentially, we compute the required candies for each condition independently, and then derive the final candy count based on maximum requirements from both arrays at each index.

Python

class Solution:
    def candy(self, ratings):
        n = len(ratings)
        if n <= 1:
            return n
        left = [1] * n
        right = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                left[i] = left[i-1] + 1
        for i in range(n-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                right[i] = right[i+1] + 1
        return sum(max(left[i], right[i]) for i in range(n))

# Example Usage
sol = Solution()
print(sol.candy([1, 0, 2]))

Java

public class CandyDistribution {
    public static int candy(int[] ratings) {
        int n = ratings.length;
        if (n <= 1) return n;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
        int totalCandy = 0;
        for (int i = 0; i < n; i++) {
            totalCandy += Math.max(left[i], right[i]);
        }
        return totalCandy;
    }

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

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> left(n, 1), right(n, 1);
    for (int i = 1; i < n; ++i) {
        if (ratings[i] > ratings[i - 1])
            left[i] = left[i - 1] + 1;
    }
    for (int i = n - 2; i >= 0; --i) {
        if (ratings[i] > ratings[i + 1])
            right[i] = right[i + 1] + 1;
    }
    int totalCandy = 0;
    for (int i = 0; i < n; ++i) {
        totalCandy += max(left[i], right[i]);
    }
    return totalCandy;
}

int main() {
    vector<int> ratings = {1, 0, 2};
    cout << candy(ratings) << endl;
    return 0;
}

JavaScript

function candy(ratings) {
    const n = ratings.length;
    const left = new Array(n).fill(1);
    const right = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
    }
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            right[i] = right[i + 1] + 1;
        }
    }
    let totalCandy = 0;
    for (let i = 0; i < n; i++) {
        totalCandy += Math.max(left[i], right[i]);
    }
    return totalCandy;
}

// Example usage
console.log(candy([1, 0, 2]));

#include <stdio.h>
#include <string.h>

int candy(int* ratings, int ratingsSize) {
    if (ratingsSize <= 1) return ratingsSize;
    int left[ratingsSize], right[ratingsSize];
    memset(left, 0, sizeof(left));
    memset(right, 0, sizeof(right));
    left[0] = 1;
    right[ratingsSize - 1] = 1;
    for (int i = 1; i < ratingsSize; i++) {
        left[i] = ratings[i] > ratings[i - 1] ? left[i - 1] + 1 : 1;
    }
    for (int i = ratingsSize - 2; i >= 0; i--) {
        right[i] = ratings[i] > ratings[i + 1] ? right[i + 1] + 1 : 1;
    }
    int totalCandies = 0;
    for (int i = 0; i < ratingsSize; i++) {
        totalCandies += left[i] > right[i] ? left[i] : right[i];
    }
    return totalCandies;
}

int main() {
    int ratings[] = {1, 0, 2};
    int size = sizeof(ratings) / sizeof(ratings[0]);
    printf("%d\n", candy(ratings, size));
    return 0;
}

using System;

public class Solution {
    public int Candy(int[] ratings) {
        int n = ratings.Length;
        if (n <= 1) return n;
        int[] left = new int[n];
        int[] right = new int[n];
        Array.Fill(left, 1);
        Array.Fill(right, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
        int totalCandies = 0;
        for (int i = 0; i < n; i++) {
            totalCandies += Math.Max(left[i], right[i]);
        }
        return totalCandies;
    }

    static void Main() {
        Solution sol = new Solution();
        int[] ratings = {1, 0, 2};
        Console.WriteLine(sol.Candy(ratings));
    }
}

The Python implementation similarly uses two lists, `left` and `right`, tracking the number of candies based on left-side and right-side conditions sequentially. The maximum value between the two arrays for each index yields the final candy distribution count.

Complexity

Time Complexity: O(n)

Space Complexity: O(n)

Try this approach in the editor

Approach 3: Two traversals

We initialize two arrays left and right, where left[i] represents the minimum number of candies the current child should get when the current child's score is higher than the left child's score, and right[i] represents the minimum number of candies the current child should get when the current child's score is higher than the right child's score. Initially, left[i]=1, right[i]=1.

We traverse the array from left to right once, and if the current child's score is higher than the left child's score, then left[i]=left[i-1]+1; similarly, we traverse the array from right to left once, and if the current child's score is higher than the right child's score, then right[i]=right[i+1]+1.

Finally, we traverse the array of scores once, and the minimum number of candies each child should get is the maximum of left[i] and right[i], and we add them up to get the answer.

Time complexity O(n), space complexity O(n). Where n is the length of the array of scores.

TypeScript

function candy(ratings: number[]): number {
    const n = ratings.length;
    const left = new Array(n).fill(1);
    const right = new Array(n).fill(1);
    for (let i = 1; i < n; ++i) {
        if (ratings[i] > ratings[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
    }
    for (let i = n - 2; i >= 0; --i) {
        if (ratings[i] > ratings[i + 1]) {
            right[i] = right[i + 1] + 1;
        }
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        ans += Math.max(left[i], right[i]);
    }
    return ans;
}

func candy(ratings []int) int {
	n := len(ratings)
	left := make([]int, n)
	right := make([]int, n)
	for i := range left {
		left[i] = 1
		right[i] = 1
	}
	for i := 1; i < n; i++ {
		if ratings[i] > ratings[i-1] {
			left[i] = left[i-1] + 1
		}
	}
	for i := n - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] {
			right[i] = right[i+1] + 1
		}
	}
	ans := 0
	for i, a := range left {
		b := right[i]
		ans += max(a, b)
	}
	return ans
}

Rust

impl Solution {
    pub fn candy(ratings: Vec<i32>) -> i32 {
        let n = ratings.len();
        let mut left = vec![1; n];
        let mut right = vec![1; n];

        for i in 1..n {
            if ratings[i] > ratings[i - 1] {
                left[i] = left[i - 1] + 1;
            }
        }

        for i in (0..n - 1).rev() {
            if ratings[i] > ratings[i + 1] {
                right[i] = right[i + 1] + 1;
            }
        }

        ratings.iter()
            .enumerate()
            .map(|(i, _)| left[i].max(right[i]) as i32)
            .sum()
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Two-Pass Solution	Time Complexity: O(n) Space Complexity: O(n)
Single-Pass with Two Arrays	Time Complexity: O(n) Space Complexity: O(n)
Two traversals	–

Approach

Complexity

Two-Pass Solution

Time Complexity: O(n)

Space Complexity: O(n)

Single-Pass with Two Arrays

Time Complexity: O(n)

Space Complexity: O(n)

Two traversals

–

Complexity analysis

Approach	Time	Space	When to Use
Two-Pass Greedy (Single Array)	O(n)	O(n)	Best general solution. Clean logic with two directional scans enforcing neighbor constraints.
Single-Pass with Two Arrays	O(n)	O(n)	Useful when you want to explicitly track left and right requirements before combining them.

Frequently asked questions

Is Candy easy or hard?

Candy is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that two directional constraints must be satisfied simultaneously, which requires careful greedy reasoning rather than a straightforward single pass.

Candy Python/Java solution

Most implementations follow the same greedy two-pass logic across languages. Python, Java, C++, C#, and JavaScript versions all initialize a candy array, perform left-to-right and right-to-left scans, then sum the results to compute the minimum candies.

How to solve Candy in O(n)?

Use a greedy approach with two directional passes. Initialize each child with one candy, scan left to right to satisfy the left neighbor condition, then scan right to left to satisfy the right neighbor condition using max updates. Summing the final array gives the minimum candies in O(n) time.

What is the best approach for Candy?

The standard solution uses a greedy two-pass strategy. First scan left to right to enforce the rule that higher-rated children get more candies than the left neighbor, then scan right to left to enforce the right neighbor rule. This approach runs in O(n) time with O(n) space and guarantees the minimum candy distribution.

Is Candy asked at Google/Amazon/Meta?

Candy is a well-known greedy interview problem and has appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of greedy constraints, array traversal, and reasoning about local vs global optimality.

What data structure is used in Candy?

The primary data structure is an array used to track candies assigned to each child. The algorithm relies on sequential traversal and greedy updates rather than complex structures like heaps or hash maps.

What is the time complexity of Candy?

The optimal solution runs in O(n) time because the ratings array is traversed only twice. Each pass performs constant-time comparisons and updates. Space complexity is O(n) for storing the candy assignments.

Candy solution and explanation

The problem

Approach overview

Approach 1: Two-Pass Solution

Approach 2: Single-Pass with Two Arrays

Approach 3: Two traversals

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Candy solution and explanation

The problem

Approach overview

Approach 1: Two-Pass Solution

Approach 2: Single-Pass with Two Arrays

Approach 3: Two traversals

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems