1431. Kids With the Greatest Number of Candies

[songyy5517]

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]

Intuition This problem mainly examines the operations of array. A simple idea is to first find the maximum in the array, and then compare each element plus extraCandies with the maximum, then store the result in a Boolean ArrayList and finally return.

[songyy5517]

Approach: Travarase the array

1. Exception handling;
2. Find the maximum in the array;
3. Compare each element plus extraCandies with the maximum value, and store the result in ArrayList;
4. Return the final result.

Complexity Analysis

• Time complexity: $O(N)$ , travarsing the whole array costs the time complexity of $O(N)$ ;
• Space complexity: $O(1)$ , additionally define constant-size variables, the $O(N)$ space of the returned List is requied, and therefore is not taken into account.

[songyy5517]

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        // Intuition: Looks simple, a strightforward idea is to first find the maximum
        // number in the array, and then travarse the array and compare each element + extra
        // with the maximum value.

        // 1. Exception handling
        if (candies == null || candies.length == 0)
            return new ArrayList();

        // 2. Find the maximum number
        int max = candies[0];
        for (int i = 0; i < candies.length; i++)
            max = candies[i] > max ? candies[i] : max;

        // 3. Compare each element + extra with the maximum
        ArrayList<Boolean> res = new ArrayList();
        for (int i = 0; i < candies.length; i++){
            res.add(candies[i] + extraCandies >= max);
        }

        return res;
    }
}

[songyy5517]

2024/5/8