Skip to content

Latest commit

 

History

History
85 lines (60 loc) · 3.7 KB

021.md

File metadata and controls

85 lines (60 loc) · 3.7 KB

1431. Kids With the Greatest Number of Candies

Difficulty: 🟢 Easy

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:

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.length
  • 2 <= n <= 100
  • 1 <= candies[i] <= 100
  • 1 <= extraCandies <= 50

Solutions

O(n) solution in Python3

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

The given solution determines the greatest number of candies among all the kids by finding the maximum value in the candies array. Then, it iterates through each kid and checks whether they can have the greatest number of candies after receiving all the extra candies.

The algorithm works as follows:

  1. Find the greatest number of candies among all the kids by calculating the maximum value in the candies array and store it in the variable greatest.
  2. Iterate through each kid's candies in the candies array:
    • Check if the sum of the kid's current candies and the extra candies is greater than or equal to the greatest number of candies.
    • Store the result (True or False) in the corresponding position of the result array.
  3. Return the result array.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the number of kids (length of the candies array). The algorithm iterates through the candies array once to find the maximum value and once again to determine the results.

The space complexity of the algorithm is O(n), where n is the number of kids (length of the candies array). The algorithm creates an additional result array to store the results for each kid.

Summary

The given solution solves the problem by finding the greatest number of candies among all the kids and then determining, for each kid, whether they can have the greatest number of candies after receiving all the extra candies. The algorithm has a time complexity of O(n) and a space complexity of O(n), making it an efficient solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.