Leetcode 1431: Kids With the Greatest Number of Candies

Input: The input consists of an array of integers `candies` where each element represents the number of candies a kid has, and an integer `extraCandies` representing the extra candies to be distributed.

Example: [3, 5, 8, 2], extraCandies = 4

Constraints:

• 2 <= n <= 100

• 1 <= candies[i] <= 100

• 1 <= extraCandies <= 50

Output: The output is a boolean array of length `n` where each element is true if, after receiving the extra candies, that kid will have the greatest number of candies, otherwise false.

Example: [true, true, true, false]

Constraints:

• The output array has the same length as the input `candies` array.

Goal: The goal is to determine whether each kid, after receiving all the extra candies, will have as many or more candies than every other kid.

Steps:

• Step 1: Find the kid with the maximum number of candies.

• Step 2: For each kid, check if adding `extraCandies` makes their total candies greater than or equal to the maximum number of candies.

Goal: The solution should efficiently handle the problem within the provided constraints.

Steps:

• The solution should work within time and space limits of up to 100 kids and 100 candies per kid.

Assumptions:

• The input will always be valid, with the number of kids being at least 2.

• Input: [3, 5, 8, 2], extraCandies = 4

• Explanation: Kid 1 will have 7 candies, Kid 2 will have 9 candies (greatest), Kid 3 will have 12 candies (greatest), and Kid 4 will have 6 candies.

• Input: [6, 2, 7, 5], extraCandies = 3

• Explanation: Kid 1 will have 9 candies (greatest), Kid 2 will have 5 candies, Kid 3 will have 10 candies (greatest), and Kid 4 will have 8 candies.

Approach: To solve this problem, we first find the maximum number of candies any kid has. Then, for each kid, we check if their total candies after adding the extra candies will be greater than or equal to this maximum.

Observations:

• The solution can be approached by finding the maximum number of candies first.

• Then, we can compare each kid's total after adding the extra candies to the maximum.

• The overall time complexity of this solution should be linear with respect to the number of kids.

Steps:

• Step 1: Identify the maximum number of candies from the input list `candies`.

• Step 2: For each kid, calculate the total candies after adding `extraCandies` and compare with the maximum candies.

• Step 3: Return the result as a boolean array indicating whether each kid will have the greatest number of candies.

Empty Inputs:

• The problem guarantees that there will be at least two kids, so there will never be empty inputs.

Large Inputs:

• Ensure the solution can handle the upper limits of `n` and the values of candies efficiently.

Special Values:

• Consider scenarios where many kids have the same number of candies or when all kids receive the extra candies.

Constraints:

• Ensure the solution works within time and space constraints.

vector<bool> kidsWithCandies(vector<int>& candies, int ext) {
    int n = candies.size();
    vector<bool> ans(n, false);
    int mx = *max_element(candies.begin(), candies.end());
    for(int i =0; i < n; i++)
        ans[i] = (candies[i]+ ext>= mx);
    return ans;
}

1 : Function Definition

vector<bool> kidsWithCandies(vector<int>& candies, int ext) {

Defines the function `kidsWithCandies` that takes a vector `candies` and an integer `ext` and returns a vector of booleans indicating whether each child can have the greatest number of candies after receiving the extra candies.

2 : Variable Initialization

    int n = candies.size();

Initializes the variable `n` to hold the size of the `candies` vector, representing the number of children.

3 : Vector Initialization

    vector<bool> ans(n, false);

Initializes a boolean vector `ans` of size `n` with all values set to `false`. This vector will store whether each child can have the greatest number of candies.

4 : Max Element Calculation

    int mx = *max_element(candies.begin(), candies.end());

Finds the maximum value in the `candies` vector, representing the greatest number of candies any child has.

5 : Loop Constructs

    for(int i =0; i < n; i++)

Starts a loop to iterate over each element in the `candies` vector.

6 : Condition Check

        ans[i] = (candies[i] + ext >= mx);

For each child, checks if the sum of their candies and the extra candies (`ext`) is greater than or equal to the maximum number of candies `mx`. If true, the corresponding entry in the `ans` vector is set to `true`.

7 : Return Statement

    return ans;

Returns the `ans` vector, which contains `true` or `false` for each child, indicating whether they can have the greatest number of candies.

Best Case: O(n), where n is the number of kids.

Average Case: O(n), as we have to iterate through all the kids.

Worst Case: O(n), since we check each kid's total candies.

Description: The time complexity is linear in the number of kids, i.e., O(n).

Best Case: O(n), as we store the result array.

Worst Case: O(n), where n is the number of kids.

Description: The space complexity is linear due to the result array.

Leetcode 1431: Kids With the Greatest Number of Candies

Explore →