Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

193. Candy

HardDay 57 of 60Greedy & Intervals

Children stand in a line and child i has a rating ratings[i]. Give each child at least one candy, and any child with a higher rating than a direct neighbour must get more candies than that neighbour. Return the minimum total number of candies.

Example 1
Input: ratings = [1,0,2]
Output: 5
Give 2, 1, 2 candies.
Example 2
Input: ratings = [1,2,2]
Output: 4
Give 1, 2, 1. The third child only needs 1 because equal ratings have no rule.
Constraints
  • 1 <= ratings.length <= 2 * 10^4
  • 0 <= ratings[i] <= 2 * 10^4
Hints
Frequently asked at: Amazon, Google, Microsoft
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min