algoadvance

Leetcode 575. Distribute Candies

Problem Statement

Given an integer array candyType representing the types of candies (where each type is represented by a unique integer), you need to determine the maximum number of different types of candies that can be eaten if you can only eat n / 2 candies (where n is the total number of candies).

In other words, you need to distribute the candies in such a way that maximizes the number of unique candy types eaten, provided that you can only eat half of the total candies.

Clarifying Questions

  1. Input Constraints:
    • What is the maximum length of candyType array?
    • Are there any constraints on the values within candyType?
  2. Output:
    • What value should be returned if given input leads to no candies being eaten?
  3. Duplicates:
    • Can there be multiple candies of the same type?

Code

import java.util.HashSet;

public class Solution {
    public int distributeCandies(int[] candyType) {
        // Calculate the maximum number of candies that the sister can eat
        int maxCandies = candyType.length / 2;
        
        // Use a HashSet to store the unique types of candies
        HashSet<Integer> uniqueCandies = new HashSet<>();
        
        // Add each candy type to the HashSet
        for (int type : candyType) {
            uniqueCandies.add(type);
        }
        
        // The sister can either eat all unique candy types or maxCandies, whichever is smaller
        return Math.min(uniqueCandies.size(), maxCandies);
    }
}

Strategy

  1. Determine the Max Candies:
    • Calculate the maximum number of candies that the sister can eat by dividing the array length by 2.
  2. Count Unique Candy Types:
    • Use a HashSet to store all unique candy types.
    • Iterate over the candyType array and add each type to the HashSet.
  3. Calculate the Result:
    • Return the minimum between the size of the HashSet (unique types) and the previously calculated maxCandies.
    • This ensures that you are optimizing for the maximum number of unique candy types eaten within the allowed quantity.

Time Complexity

This approach ensures that the solution is both time and space efficient given the constraints of typical interview problems.

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