Solution: Candy
Explore how to apply a two-pass greedy algorithm to distribute candies to children based on their ratings. This lesson helps you understand the step-by-step approach to ensure each child receives at least one candy, with higher-rated children getting more than their neighbors. You will learn to optimize the solution for time and space complexity, building practical skills in greedy techniques for coding interviews.
We'll cover the following...
Statement
You are given an array ratings where ratings[i] represents the rating of the i-th child standing in a line. Your task is to distribute candies to each child based on the following rules:
Every child must receive at least one candy.
Children with a higher rating get more candies than their neighbors.
Determine the minimum total number of candies you must distribute to satisfy the above conditions.
Constraints:
ratings.length...