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.

Description Solution Video 30:10

135. Candy

Hard49.3% acceptance24 companies

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: