Kids With the Greatest Number of Candies

Difficulty: Easy | Acceptance: 88.00% | Paid: No Topics: Array

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.

• Examples
• Constraints
• Brute Force
• Sorting
• Single Pass

Examples

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.

Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false]
Explanation: There is only 1 extra candy, so only kid 1 can have the greatest number of candies (4 + 1 = 5).

Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]

Constraints

n == candies.length
2 <= n <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

Brute Force

Intuition For each kid, we can simulate giving them the extra candies and then check if their new total is greater than or equal to every other kid’s current total.

Steps

• Iterate through the array with index i.
• Calculate potential = candies[i] + extraCandies.
• Iterate through the array again with index j.
• If potential is less than candies[j], the kid at i cannot be the greatest.
• If the inner loop completes without finding a larger value, add true to the result.

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        n = len(candies)
        result = []
        for i in range(n):
            potential = candies[i] + extraCandies
            is_greatest = True
            for j in range(n):
                if potential < candies[j]:
                    is_greatest = False
                    break
            result.append(is_greatest)
        return result

Complexity

• Time: O(n²)
• Space: O(1) (excluding output array)
• Notes: Simple to implement but inefficient for large arrays.

Sorting

Intuition If we sort the array, the greatest number of candies will be at the last index. We can then compare each kid’s potential against this maximum value.

Steps

• Create a copy of the candies array.
• Sort the copy in ascending order.
• The maximum value is the last element of the sorted array.
• Iterate through the original array and check if candies[i] + extraCandies >= max.

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        sorted_candies = sorted(candies)
        max_candies = sorted_candies[-1]
        return [c + extraCandies >= max_candies for c in candies]

Complexity

• Time: O(n log n)
• Space: O(n) (for the copy of the array)
• Notes: Sorting is overkill as we only need the maximum value.

Single Pass

Intuition We can find the maximum value in the array in a single pass. Then, in a second pass, we can determine which kids can reach or exceed this maximum with the extra candies.

Steps

• Initialize maxCandies to 0.
• Iterate through the array to find the maximum value.
• Iterate through the array again.
• For each element, check if candies[i] + extraCandies >= maxCandies.
• Store the boolean result.

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        max_candies = max(candies)
        return [c + extraCandies >= max_candies for c in candies]

Complexity

• Time: O(n)
• Space: O(1) (excluding output array)
• Notes: This is the optimal solution, requiring only two linear scans.