Kids With the Greatest Number of Candies
Problem
Given the array treats and the integer extra, where treats[i] represents the number of candies that the ith kid has. For each kid check if there is a way to distribute extra candies among the kids such that he or she can have the greatest number of candies among them. Notice that multiple kids can have the greatest number of candies.
treats = [4, 2, 7, 1], extra = 3[true, false, true, false]def kids_with_candies(treats, extra):
top = max(treats)
return [t + extra >= top for t in treats]function kidsWithCandies(treats, extra) {
const top = Math.max(...treats);
return treats.map(t => t + extra >= top);
}class Solution {
public List<Boolean> kidsWithCandies(int[] treats, int extra) {
int top = 0;
for (int t : treats) if (t > top) top = t;
List<Boolean> ans = new ArrayList<>();
for (int t : treats) ans.add(t + extra >= top);
return ans;
}
}vector<bool> kidsWithCandies(vector<int>& treats, int extra) {
int top = *max_element(treats.begin(), treats.end());
vector<bool> ans;
for (int t : treats) ans.push_back(t + extra >= top);
return ans;
}Explanation
For each child we ask: if we hand all the extra candies to this one child, could they end up with the most? The key insight is that the bar to beat is just the current maximum in the list — and we only need to find that maximum once.
So we compute top = max(treats), then for every child t we check whether t + extra >= top. The result is a list of those true/false answers.
This works because giving the extras to one child can only raise that child's count; if even with all the extras they cannot reach the existing top, no arrangement would help. Ties count as "greatest", which is why we use >= rather than >.
Example: treats = [4, 2, 7, 1], extra = 3. The max is 7. Adding 3 gives 7, 5, 10, 4, and comparing each to 7 yields [true, false, true, false].
One pass finds the max and one pass builds the answers, so the work is linear in the number of children.