Candy

Leetcode Problem 135: Candy

Problem Summary

There are n children standing in a line, each with an integer rating. You must distribute candies such that every child receives at least one candy and any child whose rating is strictly higher than a neighbor receives more candies than that neighbor. Return the minimum total number of candies needed.

The number of children is at most 20,000 and each rating is a non-negative integer up to 20,000.

Techniques

• Array
• Greedy

Solution

function candy(ratings: number[]): number {
    let leftConstraint = Array(ratings.length).fill(1);
    let rightConstraint = Array(ratings.length).fill(1);

    for (let i = 1; i < ratings.length; i++) {
        if (ratings[i] > ratings[i - 1]) {
            leftConstraint[i] = leftConstraint[i - 1] + 1
        }
    }

    for (let i = ratings.length - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            rightConstraint[i] = rightConstraint[i + 1] + 1
        }
    }

    let sum = 0

    for (let i = 0; i < ratings.length; i++) {
        sum = sum + Math.max(leftConstraint[i], rightConstraint[i])
    }

    return sum
};