Kids With the Greatest Number of Candies

Leetcode Daily Challenge (17th April, 2023)

17 April, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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.

Link: https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/

Problem Explanation with examples:-

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]
Explanation: There are 10 extra candies. Kid 1 and Kid 3 will always have the greatest number of candies, even if a different kid is given the extra candy. Kid 2 will always have the least number of candies, even if a different kid is given the extra candy.

Constraints

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

Intuition:-

Just iterate over the candies array and check if the current element + extraCandies >= max(candies) and append the result to the ans array.
Return the ans array.

Solution:-

Create a variable ans and initialize it to an empty array.
Create a variable mx and initialize it to the maximum element in the candies array.
Create a for loop which iterates over the candies array and in each iteration, we check if the current element + extraCandies >= mx.
If yes, append True to the ans array else append False to the ans array.
Return the ans array.

Code:-

JAVA Solution

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        List<Boolean> ans = new ArrayList<>();
        int mx = Integer.MIN_VALUE;
        for (int i = 0; i < candies.length; i++) {
            mx = Math.max(mx, candies[i]);
        }
        for (int i = 0; i < candies.length; i++) {
            if (candies[i] + extraCandies >= mx) {
                ans.add(true);
            } else {
                ans.add(false);
            }
        }
        return ans;
    }
}

Python Solution

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        ans = []
        mx = max(candies)
        for i in candies:
            if i+extraCandies >= mx:
                ans.append(True)
            else:
                ans.append(False)

        return ans

Complexity Analysis:-

TIME:-

The time complexity of the given Python code is O(n) where n is the length of the candies array as we iterate over the candies array once.

SPACE:-

The space complexity of the code is also O(n) where n is the length of the candies array as we create an ans array of size n. If we don't consider the space taken by the ans array, then the space complexity is O(1) as we don't use any extra space.

References:-

Array

Connect with me:-

Twitter
Github
LinkedIn
def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
ans = []
mx = max(candies)
for i in candies:
if i+extraCandies >= mx:
ans.append(True)
else:
ans.append(False)

return ans

java

python

leetcode

dsa