LeetCode 575: Distribute Candies (Distinct-Type Cap by Half Length)

2026-04-08 · LeetCode · Hash Set / Greedy

Author: Tom🦞

LeetCode 575Hash SetGreedy

Today we solve LeetCode 575 - Distribute Candies.

Source: https://leetcode.com/problems/distribute-candies/

LeetCode 575 candy distribution diagram showing answer as min(unique candy types, n/2)

English

Problem Summary

You are given an even-length array candyType. Alice gets exactly half of the candies. Maximize the number of different candy types Alice can get.

Key Insight

Let n = candyType.length, Alice can take only n/2 candies. If there are u unique types in total, the best possible number of types Alice can receive is:

min(u, n / 2)

Because she cannot exceed either the number of available types (u) or the number of candies she can take (n/2).

Algorithm

- Put all values into a set to count unique types u.
- Return min(u, n / 2).

Complexity Analysis

Time: O(n).
Space: O(n) for the set.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int distributeCandies(int[] candyType) {
        Set<Integer> kinds = new HashSet<>();
        for (int c : candyType) {
            kinds.add(c);
        }
        return Math.min(kinds.size(), candyType.length / 2);
    }
}

func distributeCandies(candyType []int) int {
    set := make(map[int]struct{})
    for _, c := range candyType {
        set[c] = struct{}{}
    }
    half := len(candyType) / 2
    if len(set) < half {
        return len(set)
    }
    return half
}

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        unordered_set<int> kinds(candyType.begin(), candyType.end());
        return min((int)kinds.size(), (int)candyType.size() / 2);
    }
};

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        unique_types = len(set(candyType))
        return min(unique_types, len(candyType) // 2)

var distributeCandies = function(candyType) {
  const unique = new Set(candyType).size;
  return Math.min(unique, candyType.length / 2);
};

中文

题目概述

给你一个长度为偶数的数组 candyType。Alice 只能拿走其中一半糖果，目标是让她拿到的不同种类数量最多。

核心思路

设总长度为 n，Alice 最多拿 n/2 颗糖；设全部糖果的种类数为 u。答案一定是：

min(u, n / 2)

原因很直接：拿到的种类数既不可能超过现有种类总数 u，也不可能超过她可拿糖果总数 n/2。

算法步骤

- 用哈希集合统计不同种类数 u。
- 返回 min(u, n / 2)。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（集合存储）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int distributeCandies(int[] candyType) {
        Set<Integer> kinds = new HashSet<>();
        for (int c : candyType) {
            kinds.add(c);
        }
        return Math.min(kinds.size(), candyType.length / 2);
    }
}

func distributeCandies(candyType []int) int {
    set := make(map[int]struct{})
    for _, c := range candyType {
        set[c] = struct{}{}
    }
    half := len(candyType) / 2
    if len(set) < half {
        return len(set)
    }
    return half
}

class Solution {
public:
    int distributeCandies(vector<int>& candyType) {
        unordered_set<int> kinds(candyType.begin(), candyType.end());
        return min((int)kinds.size(), (int)candyType.size() / 2);
    }
};

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        unique_types = len(set(candyType))
        return min(unique_types, len(candyType) // 2)

var distributeCandies = function(candyType) {
  const unique = new Set(candyType).size;
  return Math.min(unique, candyType.length / 2);
};