Problem
Given an integer array candies, wherecandies[i] represents the number of candies the ith child has, and an integer extraCandies, return a list of booleans.
For each child, determine whether giving that child all the extraCandies would make their total number of candies greater than or equal to the current maximum number of candies among all children.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
candies = [2,3,5,1,3]
extraCandies = 3Output
[true,true,true,false,true]Solution
This solution uses a Linear Scan. First, we find the maximum number of candies currently held by any child.We then iterate through the array again. For each child, we add
extraCandies to their current candies and check whether the resulting value is greater than or equal to the maximum.
If
candies[i] + extraCandies >= max, that child can have the greatest number of candies, so we add true to the result. Otherwise, we add false.
class Solution {
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
int max = 0;
for (int candy : candies) {
max = Math.max(max, candy);
}
List<Boolean> result = new ArrayList<>();
for (int candy : candies) {
if (candy + extraCandies >= max) {
result.add(true);
} else {
result.add(false);
}
}
return result;
}
}Complexity
The array is traversed twice. Each traversal takesO(n) time, so the overall time complexity is O(n).
The result list contains
n boolean values, so the output space is O(n). Apart from the output, the algorithm uses O(1) extra space.