Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 2x 2x 2x 2x 2x 2x 11x 11x 11x 11x 11x 4x 4x 11x 11x 11x 5x 5x 11x 11x 11x 2x 2x 1x 1x | // distributeCandy
// N kids stand in a line, each having an integer rating. We distribute candies following:
// • Each kid gets at least 1 candy
// • Kids with higher ratings than their neighbours get more candies.
// Find the **minimum** candies required.
// Input: [1,3,7,1]
// Output: 7
// Explanation:
// Candies: [1,2,3,1]
const distribute = (ratings: number[]): number => {
let candies: number[] = [];
const keyValuePair = Object.entries(ratings).sort(
(first, second) => first[1] - second[1]
);
for (let x = 0; x < keyValuePair.length; x++) {
const [index, value] = keyValuePair[x];
let candy = 1;
// check right kid
if (value > candies[Number(index) + 1]) {
candy = Math.max(candy, candies[Number(index) + 1] + 1);
}
// check left kid
if (value > candies[Number(index) - 1]) {
candy = Math.max(candy, candies[Number(index) + -1] + 1);
}
candies[Number(index)] = candy;
}
return candies.reduce((acc, curr) => acc + curr, 0);
};
export default distribute;
|