FastPrep
Problem · Greedy

Minimum Candies by Rating

Learn this problem
● HardCitadel logoCitadelFULLTIMEPHONE SCREEN

Problem statement

There are n children standing in a line. The integer array ratings gives each child's rating.

Give candies to the children subject to these rules:

  • Every child receives at least one candy.
  • If a child has a higher rating than an adjacent child, the higher-rated child must receive more candies.

Return the minimum total number of candies required.

Function

minimumCandies(ratings: int[]) → long

Examples

Example 1

ratings = [1,0,2]return = 5

The minimum valid allocation is [2,1,2], whose total is 5.

Example 2

ratings = [1,2,2]return = 4

The allocation [1,2,1] is valid. Equal ratings do not require different candy counts.

Constraints

  • 1 <= ratings.length <= 200000
  • -10^9 <= ratings[i] <= 10^9
  • The answer fits in a signed 64-bit integer.

More Citadel problems

drafts saved locally
public long minimumCandies(int[] ratings) {
    // write your code here
}
ratings[1,0,2]
expected5
checking account