Candy

Candy is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Sorting Based subpattern.

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

Topics and companies

Topics: Greedy.

Reported in interviews at Amazon.

How to practise Candy on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Candy in the code editor, or read the Candy editorial for a worked solution with its approach and complexity analysis.

Where Candy sits in the DSA pattern sheet

• Greedy Patterns pattern guide
• Sorting Based subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Candy

Other problems that use the same Sorting Based and Greedy Patterns techniques:

• Assign Cookies — Easy, same subpattern
• Queue Reconstruction by Height — Medium, same subpattern
• Two City Scheduling — Medium, same subpattern
• Distant Barcodes — Medium, same pattern
• Divide Intervals Into Minimum Number of Groups — Medium, same pattern
• Employee Free Time — Hard, same pattern