LeetCode 1431 - Kids With the Greatest Number of Candies

This problem asks us to determine which children could potentially have the greatest number of candies if we distribute a fixed number of extra candies to any single child.

leetcodeeasyarray

LeetCode Problem 1431

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

This problem asks us to determine which children could potentially have the greatest number of candies if we distribute a fixed number of extra candies to any single child. The input is an array candies where each element represents the number of candies a particular child has, and an integer extraCandies that represents additional candies that can be given. The output should be a boolean array result of the same length as candies, where each element is true if giving all the extraCandies to that child would make their total count greater than or equal to the current maximum, and false otherwise.

The constraints tell us that n ranges from 2 to 100, and candy counts range from 1 to 100, which is small enough to allow a simple linear scan solution. Important edge cases include situations where multiple children have the same maximum number of candies, where extraCandies is small (e.g., 1), or where a child already has the maximum number of candies without extra candies.

Approaches

The brute-force approach would involve, for each child, adding the extraCandies and then comparing this new total with every other child's candy count. While this is correct, it requires a nested loop and would take O(n²) time, which is unnecessary for the given constraints.

The optimal approach relies on the simple observation that we do not need to repeatedly compare each child against all others. Instead, we can first compute the maximum number of candies any child currently has. Then, for each child, we simply check whether their current candies plus extraCandies reaches or exceeds this maximum. This reduces the time complexity to O(n) and uses O(n) space for the result array.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Compare each child's new total against all others
Optimal O(n) O(n) Compute max once, then compare each child to max + extraCandies

Algorithm Walkthrough

  1. Initialize a variable maxCandies to the maximum value in the candies array. This represents the current greatest number of candies held by any child.

  2. Initialize an empty list result to store boolean values for each child.

  3. Iterate over each child's candy count:

  4. Add extraCandies to the child's current count.

  5. Compare this total to maxCandies.

  6. If it is greater than or equal to maxCandies, append true to result.

  7. Otherwise, append false.

  8. Return the result list.

Why it works: The algorithm works because the only thing that matters for each child is whether their total candies after adding extraCandies meet or exceed the current maximum. By precomputing the maximum once, we avoid redundant comparisons and ensure each decision is correct.

Python Solution

from typing import List

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

The Python implementation first computes the maximum candy count. Then, for each child, it checks if giving them all extra candies would make them at least equal to the maximum. This boolean expression is directly appended to the result list, which is finally returned.

Go Solution

func kidsWithCandies(candies []int, extraCandies int) []bool {
    maxCandies := candies[0]
    for _, candy := range candies {
        if candy > maxCandies {
            maxCandies = candy
        }
    }
    
    result := make([]bool, len(candies))
    for i, candy := range candies {
        result[i] = candy + extraCandies >= maxCandies
    }
    
    return result
}

The Go solution mirrors the Python approach. It first finds the maximum candy count using a simple loop. Then it initializes a boolean slice result and fills it by comparing each child's total with maxCandies. Go handles slices differently than Python lists, but the logic is identical.

Worked Examples

Example 1: candies = [2,3,5,1,3], extraCandies = 3

Child Current +Extra >= Max? Result
0 2 5 5 >= 5 true
1 3 6 6 >= 5 true
2 5 8 8 >= 5 true
3 1 4 4 >= 5 false
4 3 6 6 >= 5 true

Output: [true,true,true,false,true]

Example 2: candies = [4,2,1,1,2], extraCandies = 1

Child Current +Extra >= Max? Result
0 4 5 5 >= 4 true
1 2 3 3 >= 4 false
2 1 2 2 >= 4 false
3 1 2 2 >= 4 false
4 2 3 3 >= 4 false

Output: [true,false,false,false,false]

Example 3: candies = [12,1,12], extraCandies = 10

Child Current +Extra >= Max? Result
0 12 22 22 >= 12 true
1 1 11 11 >= 12 false
2 12 22 22 >= 12 true

Output: [true,false,true]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to compute max, then single pass to compute results
Space O(n) Boolean array of length n to store results

The time complexity is linear because each element is visited twice at most: once to find the maximum and once to generate the result. The space complexity is linear in the number of children since we must store a boolean value for each child.

Test Cases

# Provided examples
assert Solution().kidsWithCandies([2,3,5,1,3], 3) == [True, True, True, False, True]  # multiple kids reach max
assert Solution().kidsWithCandies([4,2,1,1,2], 1) == [True, False, False, False, False]  # only one kid reaches max
assert Solution().kidsWithCandies([12,1,12], 10) == [True, False, True]  # high extra candies

# Edge cases
assert Solution().kidsWithCandies([1,1], 1) == [True, True]  # all same candies, small extra
assert Solution().kidsWithCandies([100,50,50], 50) == [True, True, True]  # max and extras equal
assert Solution().kidsWithCandies([1,2,3,4,5], 0) == [False, False, False, False, True]  # no extra candies
assert Solution().kidsWithCandies([1,2,3,4,5], 50) == [True, True, True, True, True]  # extra large enough for all
Test Why
[2,3,5,1,3], 3 Standard case, multiple kids can reach max
[4,2,1,1,2], 1 Small extra candies, only one reaches max
[12,1,12], 10 Large extra candies, some children already max
[1,1], 1 Minimal input size, all equal
[100,50,50], 50 Max candy and extra sum matches others
[1,2,3,4,5], 0 No extra candies, only original max is true
[1,2,3,4,5], 50 Extra candies large enough to make all true

Edge Cases

One important edge case is when multiple children already have the maximum candy count. Without extra candies, they should all return true if the extra is large enough. The implementation handles this by comparing each child's new total with the precomputed maximum.

Another edge case is when extraCandies is zero. This tests whether the implementation correctly identifies children who are already at the maximum. The algorithm correctly returns true only for those whose candy count equals the max.

A third edge case is when extraCandies is so large that all children surpass the original maximum. The solution automatically marks all children as true because the comparison candy + extraCandies >= maxCandies naturally evaluates to true for all elements. This ensures correctness without any special handling.