1431. Kids With the Greatest Number of Candies¶
Given an integer array, where candies[i] represents the number of candies the $\(i_{th}\)$ kid has.
Return a boolean array result of length n, where result[i] is true if post giving the $\(i_{th}\)$ kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.
Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true]
Explanation: If give 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.
Intuition¶
- Find the kid with maximum candies & compare with each kid if given extra candies he will have the most or not.
Approach¶
- Iterate over the array to find the kid with maximum candies.
- Iterate over the array again to check if
candies[i] + extraCandiesis greater or equal to the kid with maximum candies.
Complexity¶
| Space Complexity | Time Complexity |
|---|---|
| $\(\text{O}(1)\)$ | $\(\text{O}(n)\)$ |
- Only extra space is used to store the result
- We itreate over the array only once
Code¶
class Solution {
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
int maxCandiesOnAKid = 0;
for(int i = 0; i < candies.length; ++i) {
maxCandiesOnAKid = Math.max(maxCandiesOnAKid,candies[i]);
}
List<Boolean> result = new ArrayList<>();
for(int i = 0; i < candies.length; ++i) {
result.add(candies[i] + extraCandies>= maxCandiesOnAKid );
}
return result;
}
}