LeetCode 1431

July 12, 2024

1431. Kids With the Greatest Number of Candies

Problem

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.

Solution

Initial Solution

Initially, I wanted to find a solution and then try to optimize it. My first thought was to use a double for loop to compare one element with all others in a list, but that could quickly lead to exponential growth.

Optimization

When I looked deeper into my brute force solution, I looked for at what point was the check changing the value. That was when we compared our calculation candies[i] + extraCandies >= candies[i] when candies[i] is the largest number in the array.

This was our optimization point. If we can find this value before our loop, we would not need to recheck every value.

Code

res = []
big = max(candies)
for i in range(len(candies)):
	if (candies[i] + extraCandies >= big):
	    res.append(True)
    else:
        res.append(False)
return res