Kids With the Greatest Number of Candies — Solution
Kids With the Greatest Number of Candies solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Kids With the Greatest Number of Candies is an easy coding problem on arrays, asked in Amazon, Google and Infosys interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon, Google, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
candies[i] is how many sweets kid i has, and you hold extraCandies more.
For each kid, answer 1 if giving them all the extra sweets would leave them with the greatest number among all the kids — possibly tied — and 0 otherwise.
Example 1
Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [1,1,1,0,1]
Explanation: Only the kid with 1 sweet still falls short of 5.
Example 2
Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [1,0,0,0,0]
Explanation: The extra sweet is not enough for anyone else to catch up to 4.
Example 3
Input: candies = [12,1,12], extraCandies = 10
Output: [1,0,1]
Constraints
n == candies.length2 <= n <= 1001 <= candies[i] <= 1001 <= extraCandies <= 50
Hints for Kids With the Greatest Number of Candies
Hint 1
The comparison is against the current maximum, which never changes.
Hint 2
Find that maximum once, before answering any kid.
Hint 3
"Greatest" allows ties, so the test is
>=.
How to solve Kids With the Greatest Number of Candies
Take the maximum once, then each kid's answer is candies[i] + extraCandies >= max.
Approach
- Scan for the largest value.
- For each kid, compare their total with that maximum.
Why it works
The extra sweets are handed to one kid at a time in each hypothetical, so the other kids' counts — and therefore the maximum — never move. That is what lets the maximum be computed once up front rather than per kid, turning an O(n²) check into O(n).
Complexity
- Time —
O(n) - Space —
O(n) for the output
Pitfalls
- Recomputing the maximum per kid is needless work.
- The comparison is
>=: tying with the greatest still counts. - The extra sweets are not shared; each kid is considered as if given all of them.
Reference solution
Python
from typing import List
def kidsWithCandies(candies: List[int], extraCandies: int) -> List[int]:
mx = max(candies)
return [1 if c + extraCandies >= mx else 0 for c in candies]Java
public static int[] kidsWithCandies(int[] candies, int extraCandies) {
int mx = 0;
for (int c : candies) mx = Math.max(mx, c);
int[] out = new int[candies.length];
for (int i = 0; i < candies.length; i++) out[i] = candies[i] + extraCandies >= mx ? 1 : 0;
return out;
}C++
vector<int> kidsWithCandies(vector<int>& candies, int extraCandies) {
int mx = 0;
for (int c : candies) mx = max(mx, c);
vector<int> out;
for (int c : candies) out.push_back(c + extraCandies >= mx ? 1 : 0);
return out;
}JavaScript
var kidsWithCandies = function(candies, extraCandies) {
var mx = 0, i;
for (i = 0; i < candies.length; i++) if (candies[i] > mx) mx = candies[i];
var out = [];
for (i = 0; i < candies.length; i++) out.push(candies[i] + extraCandies >= mx ? 1 : 0);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays