LeetCode 1431 - Kids With the Greatest Number of Candies

Table of Contents

Problem

Given an integer array candies, where each candies[i] represents the number of candies the ith kid has, and an integer extraCandies, determine if, after giving each kid all the extraCandies, they will have the greatest number of candies among all the kids. Return a boolean array result where result[i] is true if the ith kid can achieve the greatest number of candies, otherwise false.

Example 1:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true]

Example 2:

Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false]

Constraints:

• 2 <= n <= 100 (where n is the length of candies)
• 1 <= candies[i] <= 100
• 1 <= extraCandies <= 50

Approaches

Brute Force Approach:

1. Iterate Through Each Kid: For each kid, calculate the total candies they will have after receiving the extraCandies.
2. Compare With Others: For each kid, compare their total candies with every other kid’s candies to determine if they have the most.
3. Construct Result Array: Based on the comparisons, construct the boolean result array.

Optimized Approach:

1. Find Maximum Candies: Find the maximum number of candies any kid currently has.
2. Compare Against Maximum: For each kid, check if their candies plus extraCandies is at least as many as the maximum candies found. If yes, they could have the greatest number of candies.
3. Construct Result Array: Based on the comparison, construct the boolean result array.

Code Implementation

Brute Force

def kidsWithCandies(candies, extraCandies):
    n = len(candies)
    result = [False] * n

    for i in range(n):
        isMax = True
        for j in range(n):
            if i != j and candies[i] + extraCandies < candies[j]:
                isMax = False
                break
        result[i] = isMax

    return result

Optimized

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        max_candies = max(candies)
        res = [False] * len(candies)

        for i, candy in enumerate(candies):
            if candy + extraCandies >= max_candies:
                res[i] = True
        return res

Optimized Pythonic way

def kidsWithCandies(candies, extraCandies):
    maxCandies = max(candies)
    return [candy + extraCandies >= maxCandies for candy in candies]

Complexity Analysis

Brute Force:

• Time Complexity: O(n^2), where n is the number of kids. This is due to the nested iteration over the kids.
• Space Complexity: O(n) for storing the result array.

Optimized:

• Time Complexity: O(n), where n is the number of kids. The calculation involves a single pass through the list.
• Space Complexity: O(n) for the result array.

Visual Representation

Consider the input candies = [2,3,5,1,3], extraCandies = 3.

1. Brute Force Approach:

   • Iterate over each kid, checking if their candies plus extraCandies is greater than or equal to every other kid’s candy count.
   • Results in [true, true, true, false, true].

2. Optimized Approach:

   • First, find the maximum candies any kid has, which is 5.
   • Then, for each kid, check if candies[i] + extraCandies >= 5.
   • Results in `[true

, true, true, false, true]`.

Candies Array: [2, 3, 5, 1, 3]

Max Candies: 5

Calculations:
- 2 + 3 >= 5? True
- 3 + 3 >= 5? True
- 5 + 3 >= 5? True
- 1 + 3 >= 5? False
- 3 + 3 >= 5? True

Result: [True, True, True, False, True]