Lets Code Everyday -Day 8

Hello there 👋, enthusiasts.

Thanks for keeping the effort to read.Hope this will help you in some way 😊

Question - 8 :

Kids With the Greatest Number of Candies

There are n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the i<sup>th</sup> 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 i<sup>th</sup> 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]

First approach:

class Solution {
   public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
    int maxCandies = candies[0];
    for (int i = 1; i < candies.length; i++) {
        if (candies[i] > maxCandies) {
            maxCandies = candies[i];
        }
    }
    List<Boolean> result = new ArrayList<>();
    for (int i = 0; i < candies.length; i++) {
        boolean hasMostCandies = true;
        for (int j = 0; j < candies.length; j++) {
            if (i != j && candies[i] + extraCandies < candies[j]) {
                hasMostCandies = false;
                break;
            }
        }
        result.add(hasMostCandies);
    }
    return result;
}
}

Step-by-step explanation:

The function takes two inputs: an array of integers candies and an integer extraCandies.
It initializes a variable maxCandies to the first element in the candies array.
It goes through the candies array to find the maximum number of candies that any child has by comparing each element to maxCandies.
It initializes an empty ArrayList called result.
It loops through the candies array again for each child.
For each child, it sets a boolean variable hasMostCandies to true.
It loops through the candies array again for each other child, excluding the current child.
For each other child, it checks if adding the extraCandies to the current child's candies would make them have less candies than the other child. If so, it sets hasMostCandies to false and exits the loop.
It adds the value of hasMostCandies to the result ArrayList.
After looping through all the children, the result ArrayList contains a list of Booleans indicating which children can have the most candies after adding the extraCandies.
The function returns the result ArrayList as the output of the function.

The time complexity of the kidsWithCandies function is O(n^2), where n is the length of the input candies array. This is because the function loops through the candies array twice, once to find the maximum number of candies and again for each child to compare their candies with every other child's candies.

The space complexity of the function is O(n), where n is the length of the input candies array. This is because the function initializes an ArrayList of size n to store the results for each child. Additionally, it uses a constant amount of extra space to store variables like maxCandies and hasMostCandies.

Second approach:

class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int[] sortedCandies = Arrays.copyOf(candies, candies.length);
        List<Boolean> result=new ArrayList<>();
        Arrays.sort( sortedCandies);
        for(int i:candies){
            int temp=i+extraCandies;
            result.add(temp>=sortedCandies[sortedCandies.length-1]);
        }
        return result;
    }
}

Step-by-Step explanation:

The function takes two inputs: an array of integers candies and an integer extraCandies.
It creates a copy of the candies array called sortedCandies using the Arrays.copyOf method.
It initializes an empty ArrayList called list to store the result.
It sorts the sortedCandies array in ascending order using the Arrays.sort method.
It loops through each element i in the candies array.
For each element, it calculates the sum of the element and the extraCandies and stores it in a variable temp.
It compares temp with the largest element in the sortedCandies array (which is at the last index), using the >= operator.
It adds the resulting Boolean value to the list.
After looping through all the elements in the candies array, the list ArrayList contains a list of Booleans indicating which children can have the most candies after adding the extraCandies.
The function returns the list ArrayList as the output of the function.

The time complexity of the kidsWithCandies function is O(n log n), where n is the length of the input candies array. This is because the function uses the Arrays.sort method to sort the sortedCandies array, which has a time complexity of O(n log n), and then loops through each element in the candies array, which has a time complexity of O(n).

The space complexity of the function is O(n), where n is the length of the input candies array. This is because the function initializes an ArrayList of size n to store the results for each child, creates a copy of the candies array using the Arrays.copyOf method, and sorts the sortedCandies array in place. Additionally, it uses a constant amount of extra space to store variables like temp.

Conclusion:

The second implementation is better in terms of both time and space complexity.