Candy

Hard

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}