1431. Kids With the Greatest Number of Candies
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.
Solution Approach
In the provided solution, we use a simple algorithm to accomplish the task. The implementation involves the following steps:
-
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 listcandies
once and retrieves the highest value. This step is represented by the line of code:1mx = max(candies)
-
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 thecandies
list, we add the number ofextraCandies
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 theextraCandies
to each kid in turn would make their total equal to or greater than the current maximum. -
The comparison
candy + extraCandies >= mx
yields a boolean result (True
orFalse
) which indicates whether after receivingextraCandies
, that particular kid will have candies not less than the kid with the most candies. -
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
-
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.
-
With the
extraCandies
, we need to see if each kid can reach or surpass the maximum count of 5 candies. We do this by addingextraCandies
to the current number of candies each kid has and checking if it's equal to or greater than 5. -
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
. -
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
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.
max(candies)
: This call takesO(n)
time, wheren
is the number of elements in thecandies
list.- List comprehension: This also takes
O(n)
time as it iterates through the listcandies
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:
- List comprehension creates a new list with the same number of elements as the input list
candies
. This requiresO(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.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 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