1431. Kids With the Greatest Number of Candies

EasyArray
Leetcode Link

Problem Description

In this problem, we are presented with n kids, each with a certain number of candies. The candies array represents the count of candies every kid has. We are also given extraCandies, which is a number of additional candies available to distribute to the kids. Our task is to determine, for each kid, whether giving them all the extraCandies would result in them having the greatest number of candies compared to all other kids. It's important to note that more than one kid can hold the title of having the most candies if they end up with the same number of candies after distributing extraCandies. We need to return a boolean array, where each element corresponds to a kid. The value is true if the kid can have the most candies after receiving extraCandies and false otherwise.

Intuition

To solve this problem, we look to determine the highest number of candies any kid currently has, which we can do by finding the maximum value in the candies array. Once we know this maximum value, the intuition is simple: for each kid, we add extraCandies to their current number of candies and compare it with the maximum number of candies. If the sum is greater than or equal to the maximum, it means that by receiving the extraCandies, this kid could potentially have the greatest number of candies. We can do this comparison for each kid, resulting in an array of boolean values that indicate whether each kid is enabled to reach or surpass the maximum candy count with the extra candies in hand.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Solution Approach

In the provided solution, we use a simple algorithm to accomplish the task. The implementation involves the following steps:

  1. Find the maximum number of candies that any kid has by utilizing the built-in max() function, which is efficient for this purpose as it iterates through the list candies once and retrieves the highest value. This step is represented by the line of code:

    1mx = max(candies)

  2. We then iterate through the list of candies using a list comprehension—a concise way to generate a new list by applying an expression to each item in an iterable. For each element (representing each kid's candy count) in the candies list, we add the number of extraCandies and check if the new total is greater than or equal to the maximum candy count found in the first step. This step effectively checks whether distributing the extraCandies to each kid in turn would make their total equal to or greater than the current maximum.

  3. The comparison candy + extraCandies >= mx yields a boolean result (True or False) which indicates whether after receiving extraCandies, that particular kid will have candies not less than the kid with the most candies.

  4. The list comprehension returns a new list of boolean values—a direct outcome of the comparisons—which answers the problem's question for each kid. The line of code for this step looks like this:

    1return [candy + extraCandies >= mx for candy in candies]

Using this approach, the algorithm achieves a time complexity of O(n), where n is the number of elements in the candies list, since the operations involve a single scan to find the maximum and another to evaluate the condition for each kid. As for space complexity, it is also O(n), as the output is a list of n boolean values.

The utilized data structure is a simple list, and the pattern applied is a straightforward linear scan for comparison. The beauty of this solution lies in its simplicity and direct approach to determining the outcome for each kid in relation to the others.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example Walkthrough

Let's walk through a small example to demonstrate the solution approach. Assume we have five kids with the following number of candies: candies = [2, 3, 5, 1, 3], and we have extraCandies = 3 to distribute.

  1. Find the maximum number of candies that any kid has:

    1mx = max(candies)  # mx = max([2, 3, 5, 1, 3]) = 5

    The maximum number of candies with any kid is 5.

  2. With the extraCandies, we need to see if each kid can reach or surpass the maximum count of 5 candies. We do this by adding extraCandies to the current number of candies each kid has and checking if it's equal to or greater than 5.

  3. Generate the new list of boolean values by comparing the current number of candies plus extraCandies to the maximum number:

    1result = [candy + extraCandies >= mx for candy in candies]
2# result = [2+3 >= 5, 3+3 >= 5, 5+3 >= 5, 1+3 >= 5, 3+3 >= 5]
3# result = [True, True, True, False, True]

    Kid 1: Starts with 2 candies; adding 3 extra candies gives them 5, which equals the maximum. Therefore, the first element is True.

    Kid 2: Starts with 3 candies; adding 3 extra candies gives them 6, which is more than the maximum. Therefore, the second element is True.

    Kid 3: Already has the maximum of 5 candies; adding 3 more makes it 8, hence the third element is True.

    Kid 4: Starts with 1 candy; adding 3 extra candies gives them only 4, which is less than the maximum. Therefore, the fourth element is False.

    Kid 5: Starts with 3 candies; adding 3 extra candies also gives them 6, resulting in the fifth element being True.

  4. Returning this list gives us the final answer to the problem:

    1result = [True, True, True, False, True]

Using this example, each kid, except for the fourth one, can have the most candies if they receive all extraCandies. This is exactly what the boolean array indicates and is in alignment with the problem description and solution approach.

Solution Implementation

1from typing import List
2
3class Solution:
4    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
5        # Find the maximum number of candies that any child currently has
6        max_candies = max(candies)
7      
8        # Create a list of boolean values, where each value indicates whether a child
9        # can have the greatest number of candies by adding the extraCandies to their current amount
10        can_have_most_candies = [
11            (child_candies + extraCandies) >= max_candies for child_candies in candies
12        ]
13      
14        # Return the list of boolean values
15        return can_have_most_candies
16
1import java.util.List;
2import java.util.ArrayList;
3import java.util.Collections;
4
5public class Solution {
6
7    // Function to determine which kids can have the greatest number of candies
8    // after they receive an additional amount of extraCandies.
9    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
10
11        // Find the maximum number of candies that any kid currently has.
12        int maxCandies = Integer.MIN_VALUE;
13        for (int candy : candies) {
14            maxCandies = Math.max(maxCandies, candy);
15        }
16
17        // List to store the results, whether each kid can have the maximum number
18        // of candies after receiving extraCandies.
19        List<Boolean> result = new ArrayList<>();
20
21        // Loop through each kid's candies to determine if they can reach maxCandies
22        // with their current candies plus extraCandies.
23        for (int candy : candies) {
24            // If the current kid's candies plus extraCandies is greater than or
25            // equal to maxCandies, add 'true' to the result list, otherwise add 'false'.
26            result.add(candy + extraCandies >= maxCandies);
27        }
28
29        // Return the result list.
30        return result;
31    }
32}
33
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to determine which kids can have the greatest number of candies
7    // after receiving extraCandies
8    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
9        // Find the maximum number of candies any kid currently has
10        int maxCandies = *max_element(candies.begin(), candies.end());
11      
12        // Initialize a result vector to store boolean values indicating
13        // whether each kid can have the maximum number of candies
14        vector<bool> result;
15      
16        // Iterate through the number of candies each kid has
17        for (int candyCount : candies) {
18            // Check if giving extraCandies to the kid makes their total equal 
19            // or greater than maxCandies and add the result to the result vector
20            result.push_back(candyCount + extraCandies >= maxCandies);
21        }
22      
23        return result; // Return the completed result vector
24    }
25};
26
1// Function to determine which kids can have the greatest number of candies
2// after being given extra candies.
3// Parameters:
4// candies: an array of integers representing the number of candies each kid has.
5// extraCandies: an integer representing the number of extra candies to give.
6// Returns an array of booleans indicating whether each kid can have the greatest
7// number after receiving the extra candies.
8function kidsWithCandies(candies: number[], extraCandies: number): boolean[] {
9  
10    // Find the maximum number of candies any kid currently has.
11    const maxCandies = candies.reduce((max, current) => Math.max(max, current), 0);
12  
13    // Determine if each kid could have the most candies by adding the extraCandies to their current count.
14    // The result is an array of boolean values corresponding to each kid.
15    const canHaveMostCandies = candies.map(candyCount => candyCount + extraCandies >= maxCandies);
16  
17    return canHaveMostCandies;
18}
19
Not Sure What to Study? Take the 2-min Quiz：

What data structure does Breadth-first search typically uses to store intermediate states?

Time and Space Complexity

Time Complexity

The provided function involves iterating over the list candies twice - once to find the maximum value with the max function, and once in the list comprehension to check each child's candy count.

  1. max(candies): This call takes O(n) time, where n is the number of elements in the candies list.
  2. List comprehension: This also takes O(n) time as it iterates through the list candies once.

Adding both gives us a total time complexity of O(n) + O(n), which simplifies to O(n), because constant factors are ignored in big O notation.

Space Complexity

The space complexity of the function is determined by the additional space required for the output list:

  1. List comprehension creates a new list with the same number of elements as the input list candies. This requires O(n) space.

There's no other significant additional space used in the function, so the total space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫