Leetcode 1431. Kids With the Greatest Number of Candies

Problem Statement

There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the i<sup>th</sup> 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 i<sup>th</sup> 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.

Explanation

You are given a group of kids, and each kid has a certain number of candies represented by an array called candies. Additionally, you have some extra candies. The goal is to find out, for each kid, if giving them all the extra candies would make them have the greatest number of candies among all the kids.

In other words, you want to determine if adding the extra candies to a particular kid's current candies count would result in them having the most candies compared to all the other kids. It's not about making just one kid have the most candies; multiple kids can have the greatest number of candies if they receive the extra candies.

The problem asks you to return a boolean array result, where each element result[i] will be True if giving the ith kid all the extra candies would make them have the greatest number of candies among all the kids, or False otherwise.

To summarize, you are checking if each kid can potentially have the most candies by adding the extra candies to their current count, and you will return a boolean array indicating which kids meet this condition.

Greedy Algorithm Approach

To use the greedy algorithm approach, we can leverage the fact that we only need to find the maximum number of candies among all kids in the given array candies. Once we know the maximum value, we can easily determine which kids can have the greatest number of candies after receiving the extra candies.

The Algorithm:

Find the maximum number of candies (max_candies) in the candies array. This can be done by traversing through the array and keeping track of the maximum value encountered.
Initialize the result array with all values set to False.
Traverse through the candies array again and for each kid:
- Calculate the total candies the kid would have after receiving the extra candies: candies[i] + extraCandies.
- If the total candies for this kid is greater than or equal to max_candies, set the corresponding value in the result array to True. This indicates that this kid can have the greatest number of candies (or be tied for the greatest) after receiving the extra candies.
After traversing through all the kids, the result array will contain True for kids who will have the greatest number of candies (or be tied for the greatest) after receiving the extra candies, and False for the rest.
Return the result array as the final output.

The greedy algorithm approach here is considered efficient because it only requires two passes through the candies array. In the first pass, we find the maximum number of candies, and in the second pass, we determine which kids can have the greatest number of candies after receiving the extra candies.

The Code

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        maxcandi = max(candies)

        for i in range(len(candies)):
            if candies[i] + extraCandies >= maxcandi:
                candies[i] = True
            else:
                candies[i] = False

        return candies

Complexity

This approach has a time complexity of O(n) where n is the number of kids (length of the candies array), making it an optimal solution for this problem.

Finding the maximum number of candies in the candies array requires traversing through the array once. This operation has a time complexity of O(n), where n is the number of kids (length of the candies array). After finding the maximum number of candies, we again traverse through the candies array to determine which kids can have the greatest number of candies after receiving the extra candies. This operation also has a time complexity of O(n), where n is the number of kids.

Thus, the total time complexity of the code is O(n) + O(n) = O(2n). However, in Big O notation, we drop the constant factor, so the final time complexity is O(n).

The only additional data structure we are using is the result array of length n, where n is the number of kids. Therefore, the space complexity for the result array is O(n).

The greedy algorithm approach efficiently solves the problem with linear time and space complexity, making it an optimal solution for this problem.

Leetcode 1431. Kids With the Greatest Number of Candies