1431. Kids With the Greatest Number of Candies

Description

The problem requires determining whether each child in an array of candies can have the greatest number of candies if given a certain number of extra candies. The task is to return a list of boolean values where each value corresponds to whether a particular child can have the greatest number of candies after receiving the extra candies.

Intuition

The intuition behind solving this problem is to first identify the current maximum number of candies that any child has. By adding the extra candies to each child's existing count, we can compare it against the maximum to determine if they can reach or exceed this maximum value.

Approach

1. Find the Maximum: First, find the maximum number of candies any child currently has.
2. Iterate and Compare: For each child, add the extra candies to their current number of candies and check if this sum is greater than or equal to the maximum.
3. Generate Result: If the condition is met, mark True in the result list; otherwise, mark False.
4. Return the Result: Finally, return the list of boolean values.

Complexity

Time Complexity:

O(n), where n is the number of children. This is because we iterate through the list of candies twice—once to find the maximum value and once to generate the result list.

Space Complexity:

O(n), where n is the number of children. The space is used to store the boolean result list.

Code

C++

class Solution {
public:
    std::vector kidsWithCandies(std::vector& candies, int extraCandies) {
        int l = *std::max_element(candies.begin(), candies.end());
        std::vector result;

        for (int val : candies) {
            result.push_back(val + extraCandies >= l);
        }

        return result;
    }
};

Python

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

Java

public class Solution {
    public List kidsWithCandies(int[] candies, int extraCandies) {
        int l = 0;
        for (int candy : candies) {
            l = Math.max(l, candy);
        }

        List result = new ArrayList<>();
        for (int val : candies) {
            result.add(val + extraCandies >= l);
        }

        return result;
    }
}

JavaScript

var kidsWithCandies = function (candies, extraCandies) {
    let l = Math.max(...candies)

    return candies.map((val) => (val + extraCandies) >= l)

};