algoadvance

Leetcode 1431. Kids With the Greatest Number of Candies

Problem Statement

You are given an array candies where each candies[i] represents the number of candies that the i-th kid has. For each kid, check if they can have the greatest number of candies among all kids if they are given extraCandies more.

Return a boolean array result of length n, where result[i] is true if, after giving the i-th kid all the extraCandies, they will have the greatest number of candies among all the kids, else false.

Example:

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

Constraints:

Clarifying Questions

  1. Does the “greatest number of candies among all kids” mean strictly greater, or can it include being equal to the current maximum?
    • It includes being equal to the current maximum.

Strategy

  1. Find the maximum number of candies any kid currently has.
  2. Iterate over each kid’s candies count, add the extraCandies, and check if it is greater than or equal to the current maximum number of candies.
  3. Construct the resultant boolean array based on the above condition.

Code

Here is the C++ code to solve the problem:

#include <vector>
#include <algorithm>  // For std::max_element

std::vector<bool> kidsWithCandies(std::vector<int>& candies, int extraCandies) {
    // Find the maximum number of candies any kid currently has
    int maxCandies = *std::max_element(candies.begin(), candies.end());

    // Resultant boolean vector to store the result for each kid
    std::vector<bool> result(candies.size(), false);

    // Check for each kid
    for (int i = 0; i < candies.size(); ++i) {
        // If current kid's candies plus extraCandies is greater than or equal to maxCandies
        if (candies[i] + extraCandies >= maxCandies) {
            result[i] = true; // This kid can have the greatest number of candies
        }
    }
    
    return result;
}

Time Complexity

Thus, the overall time complexity is O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI