LeetCode75: Kids With the Greatest Number of Candies

Introduction

You are given an integer array candies where each element represents the number of candies a particular child has. You are also given an integer extraCandies which represents the number of extra candies you can give to any one child.

Your task is to determine for each child if they can have the greatest number of candies among all children after receiving the extra candies.

Return a list of booleans. Each boolean indicates whether the corresponding child can become the one with the maximum candies if they were given all the extra candies.

Example 1:

Input: candies = [2, 3, 5, 1, 3], extraCandies = 3
Output: [True, True, True, False, True]

Explanation:
If we give 3 extra candies to:

• Kid 1 → 2 + 3 = 5 ✅
• Kid 2 → 3 + 3 = 6 ✅
• Kid 3 → 5 + 3 = 8 ✅
• Kid 4 → 1 + 3 = 4 ❌
• Kid 5 → 3 + 3 = 6 ✅

Example 2:

Input: candies = [4, 2, 1, 1, 2], extraCandies = 1
Output: [True, False, False, False, False]

Constraints:

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

Python Solution

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

Step-by-Step Explanation

Step 1: Identify the Maximum Candy Count

maxCandies = max(candies)

• We find the maximum value in the candies list to know what the highest candy count is among all children before giving out extra candies.

Step 2: Compare Each Kid’s Potential Candy Count

result = [candy + extraCandies >= maxCandies for candy in candies]

• For each child, we check:
  • candy + extraCandies >= maxCandies
• This uses a list comprehension to create a list of booleans.
• If the condition is true, the child can have the greatest number of candies; otherwise, they can’t.

Step 3: Return the Boolean List

return result

• The final list of booleans is returned, indicating whether each child can reach or exceed the maximum candy count.

Time and Space Complexity

• Time Complexity:O(n)
  • One pass to find maxCandies, one pass to create the result list.
• Space Complexity:O(n)
  • Output list stores n boolean values.

This Python solution uses a simple and efficient one-liner to solve the problem using a list comprehension. The idea is to check whether each child, with the extra candies added, can match or exceed the maximum candy count in the original list.

Related Read

LeetCode75: Greatest Common Divisor of Strings

Resources

Kids With the Greatest Number of Candies