Minimum Number of Operations to Make Elements in Array Distinct

Difficulty: Easy | Acceptance: 71.30% | Paid: No Topics: Array, Hash Table

You are given an integer array nums. In one operation, you can remove an element from nums. Return the minimum number of operations to make all elements in nums distinct.

• Examples
• Constraints
• Approach 1: Hash Map Frequency Counting
• Approach 2: Sorting
• Approach 3: Set Difference

Examples

Example 1:

Input: nums = [1, 2, 2]
Output: 1
Explanation: After removing one occurrence of 2, nums becomes [1, 2] which has all distinct elements.

Example 2:

Input: nums = [4, 3, 2, 1, 2, 4, 3]
Output: 3
Explanation: Remove 2, 4, and 3 to make all elements distinct. Resulting array could be [4, 3, 2, 1].

Example 3:

Input: nums = [1, 2, 3, 4, 5]
Output: 0
Explanation: All elements are already distinct.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 100

Approach 1: Hash Map Frequency Counting

Intuition We can count how many times each number appears in the array. For any number that appears k times, we need to remove k - 1 of them to leave exactly one unique instance.

Steps

• Initialize a hash map to store the frequency of each number.
• Iterate through the array and populate the frequency map.
• Iterate through the values in the map. For each frequency count, add count - 1 to the total operations.
• Return the total operations.

Complexity

• Time: O(n), where n is the length of the array, as we iterate through the array and the map.
• Space: O(n), to store the frequency map in the worst case where all elements are distinct.
• Notes: This is the most standard approach for frequency-based problems.

Approach 2: Sorting

Intuition If we sort the array, duplicate elements will be adjacent to each other. We can then iterate through the sorted array and count how many times the current element is the same as the previous one.

Steps

• Sort the array in ascending order.
• Initialize a counter for operations to 0.
• Iterate from the second element to the end of the array.
• If nums[i] is equal to nums[i-1], increment the operations counter.
• Return the operations counter.

Complexity

• Time: O(n log n) due to the sorting step.
• Space: O(1) or O(n) depending on the sorting algorithm’s implementation (e.g., quicksort vs timsort).
• Notes: Sorting modifies the original array, which might not be desirable if the input needs to be preserved.

Approach 3: Set Difference

Intuition The minimum number of operations is simply the total number of elements minus the number of unique elements. We can find the number of unique elements using a Set.

Steps

• Calculate the total length of the array.
• Insert all elements into a Set to automatically remove duplicates.
• The number of operations is the difference between the total length and the size of the Set.

Complexity

• Time: O(n) on average, as set insertion operations are O(1).
• Space: O(n) to store the unique elements in the set.
• Notes: This is often the most concise and readable solution for this specific problem.