Kids With the Greatest Number of Candies
EasyPrompt
There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, denoting the number of extra candies that you have.
Return a boolean array result of length n, where result[i] is true if, after giving the ith kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.
Note that multiple kids can have the greatest number of candies.
Example 1:
Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true]
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.Example 2:
Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false]
Explanation: There is only 1 extra candy.
Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.Example 3:
Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]
Constraints:
n == candies.length2 <= n <= 1001 <= candies[i] <= 1001 <= extraCandies <= 50
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through each kid and, for each one, simulates giving them the extra candies. It then performs another full iteration through all the kids to check if the current kid's new total is the greatest.
Algorithm
- Initialize an empty boolean list
result. - Loop through each kid
ifrom0ton-1(wherenis the number of kids). - Calculate
potentialCandies = candies[i] + extraCandies. - Initialize a flag
isGreatesttotrue. - Start a nested loop through each kid
jfrom0ton-1. - Inside the nested loop, if
potentialCandies < candies[j], setisGreatesttofalseand break the inner loop. - After the inner loop, add the value of
isGreatestto theresultlist. - Return
result.
Walkthrough
The core idea is to check each kid individually against all other kids. We use a nested loop structure. The outer loop selects a kid i to give the extraCandies to. The inner loop then compares this kid's potential total (candies[i] + extraCandies) with every other kid's original candy count (candies[j]). If we find any kid j who has more candies than kid i's potential total, we know kid i cannot have the greatest number, so we mark their result as false and move to the next kid in the outer loop. If the inner loop completes without finding any kid with more candies, it means kid i can have the greatest number, and we mark their result as true.
import java.util.ArrayList;import java.util.List; class Solution { public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) { int n = candies.length; List<Boolean> result = new ArrayList<>(n); for (int i = 0; i < n; i++) { int potentialCandies = candies[i] + extraCandies; boolean isGreatest = true; for (int j = 0; j < n; j++) { if (potentialCandies < candies[j]) { isGreatest = false; break; } } result.add(isGreatest); } return result; }}Complexity
Time
O(n^2), where `n` is the number of kids. For each of the `n` kids, we iterate through all `n` kids again to check if they have the greatest number of candies.
Space
O(n) to store the output `result` list. If the output list is not considered extra space, the complexity is O(1).
Trade-offs
Pros
Simple to understand and implement directly from the problem's definition.
Cons
Inefficient due to the nested loop, leading to a quadratic time complexity.
Performs many redundant comparisons.
A more efficient approach is to first determine the maximum number of candies any kid currently has. Then, for each kid, we only need to check if their candy count plus the extra candies is greater than or equal to this pre-calculated maximum.
Algorithm
- Initialize a variable
maxCandiesto 0. - Iterate through the
candiesarray to find the maximum number of candies any kid has and store it inmaxCandies. - Initialize an empty boolean list
result. - Iterate through the
candiesarray again. - For each
candycount, check ifcandy + extraCandies >= maxCandies. - If the condition is true, add
truetoresult. Otherwise, addfalse. - Return the
resultlist.
Walkthrough
This method avoids the nested loop by realizing that a kid can have the greatest number of candies if, after receiving the extra candies, their total is at least as large as the maximum number of candies any kid had initially. The algorithm consists of two main steps:
- First Pass: Iterate through the
candiesarray once to find the maximum value, let's call itmaxCandies. - Second Pass: Iterate through the
candiesarray again. For each kidi, calculatecandies[i] + extraCandiesand compare it withmaxCandies. Ifcandies[i] + extraCandies >= maxCandies, the result for this kid istrue; otherwise, it'sfalse.
This reduces the problem from n comparisons for each kid to just one comparison for each kid after an initial pass to find the maximum.
import java.util.ArrayList;import java.util.List; class Solution { public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) { int n = candies.length; int maxCandies = 0; // First pass: find the maximum number of candies for (int candy : candies) { if (candy > maxCandies) { maxCandies = candy; } } List<Boolean> result = new ArrayList<>(n); // Second pass: determine if each kid can have the greatest number for (int candy : candies) { if (candy + extraCandies >= maxCandies) { result.add(true); } else { result.add(false); } } return result; }}Complexity
Time
O(n), where `n` is the number of kids. We make two separate passes through the array, one to find the maximum (O(n)) and one to build the result list (O(n)). The total time is O(n) + O(n) = O(n).
Space
O(n) to store the output `result` list. If the output list is not considered extra space, the complexity is O(1).
Trade-offs
Pros
Highly efficient with linear time complexity.
It's the optimal solution for this problem.
Cons
Requires two passes over the input array, though this doesn't affect the overall asymptotic complexity.
Solutions
Solution
class Solution {public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) { int mx = 0; for (int candy : candies) { mx = Math.max(mx, candy); } List<Boolean> res = new ArrayList<>(); for (int candy : candies) { res.add(candy + extraCandies >= mx); } return res; }}class Solution {public: vector<bool> kidsWithCandies(vector<int> &candies, int extraCandies) { int mx = *max_element(candies.begin(), candies.end()); vector<bool> res; for (int candy : candies) { res.push_back(candy + extraCandies >= mx); } return res; }};class Solution: def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]: mx = max(candies) return [candy + extraCandies >= mx for candy in candies]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.