DSA · Greedy · #48
Candy
Module 51 · difficulty 4/5·⏱ 30:00starts on first keystroke
There are `n` children standing in a line, each with a rating value given in the integer array `ratings`. You are giving candies to these children subject to two rules: - Every child must get at least one candy. - A child with a higher rating than an immediate neighbor must get more candies than that neighbor. Implement `candy(ratings)` that returns the **minimum** number of candies you must distribute.
Examples
ratings = [1,0,2]→5— Distribute candies as [2,1,2].ratings = [1,2,2]→4— Distribute as [1,2,1]. The third child gets 1 candy; the rule only constrains strictly higher ratings, so equal neighbors are independent.ratings = [1,3,2,2,1]→7— Distribute as [1,2,1,2,1].
Constraints
- · n == ratings.length
- · 1 <= n <= 2 * 10^4
- · 0 <= ratings[i] <= 2 * 10^4
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.