Scale Engineer

Kids With the Greatest Number of Candies

Easy
#1324Time: 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).1 company
Data structures
Array
Companies
Infosys

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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).

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem