Algorithm Problem Review #5: Arrays and Candy

Photo by Amit Lahav on Unsplash

A new week and a new problem. I found this problem on LeetCode. I had fun with this problem mainly because it had something to do with sweets.

Problem 1431: Kids With the Greatest Number of Candies

Given the array candies and the integer extraCandies, where candies[i] represents the number of candies that the ith kid has.

For each kid check if there is away to distribute extraCandies among the kids such that he or she can have the greatest number of candies among them. Notice that multiple kids can have the greatest number of candies

Example

Input: candies = [2, 3, 5, 1, 3], extraCandies = 3
Output: [true, true, true, false, true]
Explanation:
Kid 1 has 2 candies and if he or she receives all extra candies (3) will have 5 candies — — the greatest number of candies among the kids.
Kid 2 has 3 candies and if he or she receives at least 2 extra candies will have the greatest number of candies among the kids.
Kid 3 has 5 candies and this is already the greatest number of candies among the kids.
Kid 4 has 1 candy and even if he or she receives all extra candies will only have 4 candies.
Kid 5 has 3 candies and if he or she receives at least 2 extra candies will have the greatest number of candies among the kids.

Input: candies = [4, 2, 1, 1, 2], extraCandies = 1
Output: [true, false, false, false, false]
Explanation: There is only 1 extra candy, therefore only kid 1 will have the greatest number of candies among the kids regardless of who takes the extra candy.

Constraints:

  • 2 <= candies.length <= 100
  • 1 <= candies[i] <= 100
  • 1 <= extraCandies <= 50
function kidsWithCandies(candies, extraCandies){}

My Process

Understanding The Problem

I need to create a function that accepts an array candies and an integer extraCandies. Each element in candies represents how much candy that nth child has. The integer extraCandies represents is self-explanatory — how much extra candy we have. I want to return an array that contains only boolean values of true and false. The index of the returned array corresponds to the index of the child in candies array. In the returned array, the child will have a true value if they have the greatest amount of candy when given the extraCandies value and a false value if they don’t.

Breaking it Down

Laying out my comments on what I need to do.

function kidsWithCandies(candies, extraCandies){// do something// return an array with true/false values for each kid in the array if they can have the greatest # of candies if given the extraCandies.}

“Do something”: My plan is to give each kid in the candies array ALL of the extraCandies and checking to see if they have the greatest amount of candies compared to the other kids in the array.

After doing some research, I found a built-in JavaScript object called Math that can be very helpful here. Math is used to perform mathematical tasks like rounding up, getting the sine of a number and — what we’ll be using today — getting the largest number in a group of zero or more numbers. Here is the function we’ll use to do that Math.max().

function kidsWithCandies(candies, extraCandies){// do something
// give each kid in the array all the candies and compare if they have the most compared to the other kids
for(kid of candies){
if(kid + extraCandies >= Math.max(...candies) ){
console.log("I have the most")
} else {
console.log("I do not have the most")
}
}
// return an array with true/false values for each kid in the array if they can have the greatest # of candies if given the extraCandies.}

Now we have a function that gives us a lot of console logs that say “I have the most” and/or “I don’t have the most.” Now, this is the easy part. We don’t want to have our function return console logs, we want an array of true/false values. So let's make our array.

I will make an empty array inside the function and call it greatestCandies and then replace the console logs so I can push the boolean true or false into the greatestCandies array. If they have the most candies — true. If they don’t — false.

And finally, return the greatestCandies array.

function kidsWithCandies(candies, extraCandies){// do something  // create empty array
let greatestCandies = []
// give each kid in the array all the candies and compare if they have the most compared to the other kids
// replace console logs and push true/false into array
for(kid of candies){
if(kid + extraCandies >= Math.max(...candies) ){
greatestCandies.push(true)
} else {
greatestCandies.push(false)
}
}
// return an array with true/false values for each kid in the array if they can have the greatest # of candies if given the extraCandies.
return greatestCandies
}

SOLVED —O(n) time complexity

function kidsWithCandies(candies, extraCandies){  let greatestCandies = []  for(kid of candies){
if(kid + extraCandies >= Math.max(...candies) ){
greatestCandies.push(true)
} else {
greatestCandies.push(false)
}
}
return greatestCandies}

My Thoughts

I thoroughly enjoyed working on this problem. Not only was it a feel-good problem, but it also gave me more insight and helped me learn more about the built-in Math object.

Happy Coding!!

Photo by Chris Barbalis on Unsplash

Software Engineering Student at Flatiron NYC. Learning day by day 💻