Top Interview 150
Distributing candies while respecting certain rules is a great problem to test greedy algorithms. Letโs solve LeetCode 135: Candy, where the goal is to determine the minimum number of candies needed to satisfy the given constraints.
๐ Problem Description
You are given an array ratings
, where each element represents a childโs rating. You need to distribute candies to these children while meeting the following rules:
- Each child must get at least 1 candy.
- Children with higher ratings must receive more candies than their neighbors. Return the minimum number of candies required.
๐ก Examples
Example 1
Input: ratings = [1,0,2]
Output: 5
Explanation: The distribution is [2,1,2].
Example 2
Input: ratings = [1,2,2]
Output: 4
Explanation: The distribution is [1,2,1].
๐ JavaScript Solution
This problem can be efficiently solved using a two-pass greedy approach:
- Start by assigning
1 candy to everyone
. - Traverse the array
left-to-right
to ensure each child has more candies than the one on the left if their rating is higher. - Traverse the array
right-to-left
to ensure each child has more candies than the one on the right if their rating is higher.
Implementation
var candy = function(ratings) {
const n = ratings.length;
const candies = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
return candies.reduce((total, num) => total + num, 0);
};
๐ How It Works
- Initialize candies:
- Every child starts with 1 candy because each must have at least one.
- Left-to-right pass:
- If a childโs rating is higher than their left neighbor, give them more candies than the left neighbor.
- Right-to-left pass:
- If a childโs rating is higher than their right neighbor, ensure they have more candies than the right neighbor.
- Use
Math.max()
to ensure both conditions are satisfied.
- Sum up candies:
- Calculate the total candies needed after both passes.
๐ Complexity Analysis
- > Time Complexity:
O(n)
, where n is the number of children.- The two passes (left-to-right and right-to-left) each take O(n).
- > Space Complexity:
O(n)
, for thecandies
array.
๐ Dry Run
Input: ratings = [1,0,2]
โจ Pro Tips for Interviews
- Understand constraints: Clarify the rules and confirm if ratings can have duplicates (yes, they can).
- Explain the two-pass approach: Highlight why two passes are necessary to satisfy both left and right neighbor conditions.
- Edge cases:
- Single child (
ratings = [1] โ 1
). - Increasing or decreasing ratings (
ratings = [1,2,3]
โ6
).
- Single child (
๐ Learn More
Check out the full explanation and code walkthrough on my Dev.to post:
๐ Gas Station- JavaScript Solution
How would you optimize this further? Letโs discuss below! ๐
Top comments (1)
Follow Me on GitHub ๐
If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.
Don't forget to follow for more updates!