Skip to main content
Talentd

Candy - Solution & Explanation

HardArrayGreedy23 min readAsked at: Amazon, Microsoft, Goldman Sachs +21
Practice this problem

Problem Statement

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 * 104
  • 0 <= ratings[i] <= 2 * 104

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.

This solution uses two passes over the ratings array.

In the first pass, we move from left to right, ensuring that each child has more candies than their left neighbor if they have a higher rating. In the second pass, we move from right to left, adjusting candies to maintain the higher-rating-more-candies constraint relative to their right neighbor. Finally, we sum up the candy totals.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - where n is the number of children, because we make two linear passes through the ratings.

Space Complexity: O(n) - where n is the number of children, due to the storage of candies array.

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.

The solution employs two arrays `left` and `right` which are used to store candies count by considering the rating increase from left to right and right to left respectively. Finally, for each child, the maximum from `left` and `right` arrays is chosen as the candy count.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pass Solution

Time Complexity: O(n) - where n is the number of children, because we make two linear passes through the ratings.

Space Complexity: O(n) - where n is the number of children, due to the storage of candies array.

Single-Pass with Two Arrays

Time Complexity: O(n)

Space Complexity: O(n)

Two traversals—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 ArraysO(n)O(n)Useful when you want to explicitly track left and right requirements before combining them.

Video Solution

L12. Candy | Slope Approach Intuition Based • take U forward • 155,873 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Candy with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if Grid Satisfies Conditions

Next

Minimize Maximum Value in a Grid