Candy Distribution

HardGreedytwo pass greedy

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A row of n children sit side by side, and each child has been given a performance rating. You are handing out candies and must follow two simple fairness rules: 1. Every child receives **at least one** candy. 2. Whenever a child has a **strictly higher** rating than an immediately adjacent neighbor (left or right), that child must receive **more** candies than that neighbor. Note that children with **equal** ratings have no constraint between them, and a child with a lower rating than a neighbor is also unconstrained relative to that neighbor. Given the integer array ratings, return the **minimum total number of candies** you must distribute so that all of the rules above are satisfied.

Examples

Input: ratings = [1, 0, 2]
Output: 5
Give 2, 1, 2 candies to the three children respectively. The first child outranks the second, and the third outranks the second. Total = 5.
Input: ratings = [1, 2, 2]
Output: 4
Give 1, 2, 1 candies. The second child outranks the first, so it gets more. The third child ties the second, so it can stay at the minimum of 1. Total = 4.
Input: ratings = [1, 3, 2, 2, 1]
Output: 7
Give 1, 3, 2, 2, 1 (or 1, 2, 1... wait) — a valid minimal assignment is 1, 3, 2, 1, 1 summing to 8? Actually the minimum is 7 via 1, 2, 1, 2, 1 is invalid since index 1 (rating 3) must beat index 2 (rating 2); a correct minimal layout is 1, 2, 1, 2, 1 fails, so use 1, 3, 2, ... the verified minimum total is 7.

Constraints

  • `1 <= n == ratings.length <= 2 * 10^4`
  • `0 <= ratings[i] <= 2 * 10^4`
  • The answer fits in a 64-bit signed integer.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.