Candy
Problem
Children stand in a line with ratings. Every child gets at least one candy, and a child with a higher rating than a neighbour must get more candies than that neighbour. Return the minimum total number of candies.
Example 1
Input: [1, 0, 2] Output: 5
2, 1, 2.
Example 2
Input: [1, 2, 2] Output: 4
1, 2, 1 — equal ratings have no constraint.
Test cases
Case 1
Input: [1,0,2] Expected: 5
Case 2
Input: [1,2,2] Expected: 4
Case 3
Input: [1,3,2,2,1] Expected: 7
View solutionHide solution1 approach
1. Two passes
Time O(n)Space O(n)
Left to right: give one more than the left neighbour if rated higher. Right to left: take the max with one more than the right neighbour if rated higher. Each pass satisfies one side’s constraint without breaking the other.
function candy(ratings) { const n = ratings.length, c = new Array(n).fill(1); for (let i = 1; i < n; i++) if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1; for (let i = n - 2; i >= 0; i--) if (ratings[i] > ratings[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1); return c.reduce((a, b) => a + b, 0);}