Distribute Candies

Distribute Candies - LeetCode

Problem

Given an array of candies, determine the maximum amount of different candies one can eat if the maximum amount of candies to be consumed is n / 2, where n is the amount of candies.

Example:

Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.

Solutions

Brute Force

A theoretical valid first attempt, but it’s runtime is too long. We try to create an array of unique candies and either push that length or that of maxCandies. A double for loop is often the worst way of solving these types of problems.

Because it’s a double for loop, its time complexity is O(n²) and space complexity O(n). There’s got to be a better way!

More Optimal Brute Force

A more optimal way of doing the previous method is adding the condition UniqueCandies.length <…