Distribute Candies

Problem

• Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

Go Solution

func distributeCandies(candyType []int) int {
    n := len(candyType) / 2
    m := make(map[int]bool)
    for _, num := range candyType {
        m[num] = true
        if len(m) >= n {
            return n
        }
    }

    return min(len(m), n)
}

func min(a,b int) int {
    if a < b {
        return a
    }
    return b
}

Performance

• Runtime beats: 80%
• Memory beats: 75%

Complexity

• Time: O(n)
• Space: O(n)