There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Every single child must have at least one candy.
Children with a higher rating than their immediate neighbors must get more candies than those neighbors.
Return the absolute minimum number of candies you need to distribute to satisfy all conditions.
Note: An immediate neighbor means the child directly next to the current child. For a child at index i, the immediate neighbors are i - 1 and i + 1 when those positions exist.
Example 1
Input: ratings = [1, 0, 2]
Output: 5
Explanation: The candies can be distributed as [2, 1, 2].
The child with rating 1 gets more candies than the child with rating 0, and the child with rating 2 also gets more candies than the child with rating 0.
Total candies = 2 + 1 + 2 = 5.
Example 2
Input: ratings = [1, 2, 2]
Output: 4
Explanation: The candies can be distributed as [1, 2, 1].
The second child has a higher rating than the first child, so the second child gets more candies. The second and third children have equal ratings, so no extra candy rule is needed between them.
Total candies = 1 + 2 + 1 = 4.
Approach
Each child can be constrained by the left neighbor, the right neighbor, or both. If a child has a higher rating than the left neighbor, that child must receive one more candy than the left neighbor. If a child has a higher rating than the right neighbor, that child must receive one more candy than the right neighbor. Equal or lower ratings do not create this requirement.
These two requirements can be measured separately. One value records the minimum candies needed to satisfy the left-side relationship, and another value records the minimum candies needed to satisfy the right-side relationship.
For each child, the larger of the two requirements is enough to satisfy both sides. Taking anything smaller may break one neighbor rule, and taking anything larger adds candies that are not needed.
Algorithm
Give
1candy to every child at the beginning. This is the minimum allowed by the problem, so the solution starts from the smallest valid base.Move from left to right. Whenever the current child has a higher rating than the child on the left, give the current child one more candy than the left child. This step makes sure all increasing slopes from left to right are valid.
Move from right to left. Whenever the current child has a higher rating than the child on the right, the current child may need more candies than before.
While fixing the right-side rule, take the maximum of the current candy count and
right child candies + 1. This is needed because the child may already have enough candies due to the left-side rule, and lowering that value would break the earlier work.Add all candy counts at the end. The sum gives the minimum total because candies were increased only when a neighbor rule forced an increase.
Dry Run
Candies Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* * Finds the minimum candies needed so every child * satisfies both adjacent rating rules. */ int candy(vector<int>& ratings) { int n = ratings.size(); // Each child must receive at least one candy. vector<int> candies(n, 1); for (int i = 1; i < n; i++) { // If the current child has a higher rating // than the left child, they need more candies. if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] + 1; } } for (int i = n - 2; i >= 0; i--) { // If the current child has a higher rating // than the right child, the right-side rule // must also be satisfied. if (ratings[i] > ratings[i + 1]) { candies[i] = max(candies[i], candies[i + 1] + 1); } } // This stores the minimum total candies required. int totalCandies = 0; for (int candyCount : candies) { totalCandies += candyCount; } return totalCandies; }};// Driver code startsint main() { vector<int> ratings = {1, 0, 2}; Solution sol; cout << sol.candy(ratings) << endl; return 0;}Complexity Analysis
Time Complexity: O(n), where n is the number of children. The ratings array is scanned twice, and the candies are summed once.
Space Complexity: O(n), because an extra candies array is used to store the candy count for each child.
Interview follow-up Questions
The problem constraints specifically state that children with a higher rating get more candies. If two adjacent children have the exact same rating, there is no rule forcing them to have the same amount of candies. To keep our total minimum, we act greedily and reset the new child's candy count back to the absolute minimum of 1.
Be the first to add a comment.