#1431
Kids With the Greatest Number of Candies
Easy Array & List
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Each kid has some candies. For each kid, say whether giving them all the extra candies would make their count at least as large as every other kid's.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: if we give a kid all the extra candies, do they reach the current maximum?
Why this works: find the maximum once, then each kid is one comparison. Ties count as "greatest".
Example: candies = [2, 3, 5, 1, 3], extra = 3, max = 5
2+3=5 ≥ 5 true3+3=6 true, 5+3=8 true1+3=4 false, 3+3=6 true[true, true, true, false, true]
✦Hints open one at a time
Find the current maximum first.
Kid i qualifies if candies[i] + extra >= max.
↗Approach
One pass to find the maximum, a second pass to build a List<Boolean>. Two separate passes are still O(n).
</>Solution (Java)
import java.util.*;
class Solution {
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
int max = 0;
for (int c : candies) max = Math.max(max, c);
List<Boolean> ans = new ArrayList<>();
for (int c : candies) ans.add(c + extraCandies >= max); // autoboxing boolean -> Boolean
return ans;
}
}!Common mistake
Using > instead of >=; tying with the maximum counts as "greatest".
Complexity
- Time: O(n).
- Space: O(n) for the output.
