# Kids With the Greatest Number of Candies
**Difficulty:** EASY
[External](https://leetcode.com/problems/kids-with-the-greatest-number-of-candies)
Canonical: https://scaleengineer.com/dsa/problems/kids-with-the-greatest-number-of-candies
**Data structures:** Array
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
There are `n` kids with candies. You are given an integer array `candies`, where each `candies[i]` represents the number of candies the `ith` kid has, and an integer `extraCandies`, denoting the number of extra candies that you have.

Return _a boolean array_ `result` _of length_ `n`_, where_ `result[i]` _is_ `true` _if, after giving the_ `ith` _kid all the_ `extraCandies`_, they will have the **greatest** number of candies among all the kids_ _, or_ `false` _otherwise_.

Note that **multiple** kids can have the **greatest** number of candies.

**Example 1:**

**Input:** candies = [2,3,5,1,3], extraCandies = 3
**Output:** [true,true,true,false,true] 
**Explanation:** If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

**Example 2:**

**Input:** candies = [4,2,1,1,2], extraCandies = 1
**Output:** [true,false,false,false,false] 
**Explanation:** There is only 1 extra candy.
Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.

**Example 3:**

**Input:** candies = [12,1,12], extraCandies = 10
**Output:** [true,false,true]

**Constraints:**

* `n == candies.length`
* `2 <= n <= 100`
* `1 <= candies[i] <= 100`
* `1 <= extraCandies <= 50`

# Approaches
## Brute Force with Nested Loops
This approach iterates through each kid and, for each one, simulates giving them the extra candies. It then performs another full iteration through all the kids to check if the current kid's new total is the greatest.
**Time:** O(n^2), where `n` is the number of kids. For each of the `n` kids, we iterate through all `n` kids again to check if they have the greatest number of candies. · **Space:** O(n) to store the output `result` list. If the output list is not considered extra space, the complexity is O(1).
**Pros:** Simple to understand and implement directly from the problem's definition.
**Cons:** Inefficient due to the nested loop, leading to a quadratic time complexity.; Performs many redundant comparisons.
### Explanation
The core idea is to check each kid individually against all other kids. We use a nested loop structure. The outer loop selects a kid `i` to give the `extraCandies` to. The inner loop then compares this kid's potential total (`candies[i] + extraCandies`) with every other kid's original candy count (`candies[j]`). If we find any kid `j` who has more candies than kid `i`'s potential total, we know kid `i` cannot have the greatest number, so we mark their result as `false` and move to the next kid in the outer loop. If the inner loop completes without finding any kid with more candies, it means kid `i` can have the greatest number, and we mark their result as `true`.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int n = candies.length;
        List<Boolean> result = new ArrayList<>(n);

        for (int i = 0; i < n; i++) {
            int potentialCandies = candies[i] + extraCandies;
            boolean isGreatest = true;
            for (int j = 0; j < n; j++) {
                if (potentialCandies < candies[j]) {
                    isGreatest = false;
                    break;
                }
            }
            result.add(isGreatest);
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty boolean list `result`.
- Loop through each kid `i` from `0` to `n-1` (where `n` is the number of kids).
- Calculate `potentialCandies = candies[i] + extraCandies`.
- Initialize a flag `isGreatest` to `true`.
- Start a nested loop through each kid `j` from `0` to `n-1`.
- Inside the nested loop, if `potentialCandies < candies[j]`, set `isGreatest` to `false` and break the inner loop.
- After the inner loop, add the value of `isGreatest` to the `result` list.
- Return `result`.

## Optimized Approach: Find Maximum First
A more efficient approach is to first determine the maximum number of candies any kid currently has. Then, for each kid, we only need to check if their candy count plus the extra candies is greater than or equal to this pre-calculated maximum.
**Time:** O(n), where `n` is the number of kids. We make two separate passes through the array, one to find the maximum (O(n)) and one to build the result list (O(n)). The total time is O(n) + O(n) = O(n). · **Space:** O(n) to store the output `result` list. If the output list is not considered extra space, the complexity is O(1).
**Pros:** Highly efficient with linear time complexity.; It's the optimal solution for this problem.
**Cons:** Requires two passes over the input array, though this doesn't affect the overall asymptotic complexity.
### Explanation
This method avoids the nested loop by realizing that a kid can have the greatest number of candies if, after receiving the extra candies, their total is at least as large as the maximum number of candies any kid had initially. The algorithm consists of two main steps:

1.  **First Pass:** Iterate through the `candies` array once to find the maximum value, let's call it `maxCandies`.
2.  **Second Pass:** Iterate through the `candies` array again. For each kid `i`, calculate `candies[i] + extraCandies` and compare it with `maxCandies`. If `candies[i] + extraCandies >= maxCandies`, the result for this kid is `true`; otherwise, it's `false`.

This reduces the problem from `n` comparisons for each kid to just one comparison for each kid after an initial pass to find the maximum.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int n = candies.length;
        int maxCandies = 0;
        // First pass: find the maximum number of candies
        for (int candy : candies) {
            if (candy > maxCandies) {
                maxCandies = candy;
            }
        }

        List<Boolean> result = new ArrayList<>(n);
        // Second pass: determine if each kid can have the greatest number
        for (int candy : candies) {
            if (candy + extraCandies >= maxCandies) {
                result.add(true);
            } else {
                result.add(false);
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize a variable `maxCandies` to 0.
- Iterate through the `candies` array to find the maximum number of candies any kid has and store it in `maxCandies`.
- Initialize an empty boolean list `result`.
- Iterate through the `candies` array again.
- For each `candy` count, check if `candy + extraCandies >= maxCandies`.
- If the condition is true, add `true` to `result`. Otherwise, add `false`.
- Return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
    int mx = 0;
    for (int candy : candies) {
      mx = Math.max(mx, candy);
    }
    List<Boolean> res = new ArrayList<>();
    for (int candy : candies) {
      res.add(candy + extraCandies >= mx);
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<bool> kidsWithCandies(vector<int> &candies, int extraCandies) {
    int mx = *max_element(candies.begin(), candies.end());
    vector<bool> res;
    for (int candy : candies) {
      res.push_back(candy + extraCandies >= mx);
    }
    return res;
  }
};

```

### Python

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

```