algoadvance

Leetcode 1431. Kids With the Greatest Number of Candies

Problem Statement

You are given an array candies and an integer extraCandies, where candies[i] represents the number of candies that the i-th kid has. For each kid, check if there is a way to distribute the extraCandies among the kids such that after giving the extraCandies to any one of them, they will have the greatest number of candies among all the kids. Note that multiple kids can have the greatest number of candies.

Return a boolean array result of length n, where result[i] is true if, after giving the extraCandies to the i-th kid, they can have the greatest number of candies among all the kids, or false otherwise.

Example

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true]

Explanation:
Kid 1 has 2 + 3 = 5 candies total.
Kid 2 has 3 + 3 = 6 candies total.
Kid 3 has 5 + 3 = 8 candies total.
Kid 4 has 1 + 3 = 4 candies total.
Kid 5 has 3 + 3 = 6 candies total.

Only Kid 3 has the greatest number of candies among the kids.

Constraints

Clarifying Questions

  1. Are there any negative values in the input?
    • No, the input values will only be positive integers.
  2. Can the same number of candies be held by multiple kids after adding the extraCandies?
    • Yes, multiple kids can have the same number of candies, and therefore multiple kids can end up with the greatest number.

Strategy

  1. Find the maximum number of candies any kid currently has.
  2. For each kid, add extraCandies to their current candies.
  3. Check if the new value (current candies + extraCandies) is greater than or equal to the maximum candies found in step 1.
  4. Return a list of boolean values indicating the result for each kid.

Code

import java.util.List;
import java.util.ArrayList;

public class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        List<Boolean> result = new ArrayList<>();
        int maxCandies = 0;
        
        // Find the maximum candies any kid currently has
        for (int candy : candies) {
            if (candy > maxCandies) {
                maxCandies = candy;
            }
        }
        
        // Determine if each kid can have the greatest number of candies
        for (int candy : candies) {
            if (candy + extraCandies >= maxCandies) {
                result.add(true);
            } else {
                result.add(false);
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] candies = {2, 3, 5, 1, 3};
        int extraCandies = 3;
        System.out.println(sol.kidsWithCandies(candies, extraCandies));
    }
}

Time Complexity

Explanation

  1. Iterate through the candies array to find the maximum number of candies (maxCandies) any kid currently has.
  2. Iterate through the candies array again to check for each kid if their candies + extraCandies is greater than or equal to maxCandies.
  3. Store the result (true or false) in a list and return it.

This problem is efficiently solved with a linear scan approach, ensuring the time complexity remains O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI