3396. Minimum Number of Operations to Make Elements in Array Distinct

EasyArrayHash Table

Problem Description

You are given an integer array nums. You need to ensure that the elements in the array are distinct. To achieve this, you can perform the following operation any number of times:

Remove 3 elements from the beginning of the array. If the array has fewer than 3 elements, remove all remaining elements.

Note that an empty array is considered to have distinct elements. Return the minimum number of operations needed to make the elements in the array distinct.

Intuition

To solve the problem, the goal is to make all elements of the array nums distinct with the minimum number of operations. Since we can only remove either 3 elements from the start of the array or all of them if fewer than 3 are left, we must find when duplicates stop being an issue.

The approach involves examining the array from end to start. At each step, record the elements encountered using a hash set. If an element is found in this set, it signifies a repetition, prompting a series of operations to clear these repeating components out. The needed operations equate to removing three elements repeatedly from the leading part of the list, calculated by integer division of the current index by 3, then plus one to account for zero-based index.

Thus, the algorithm proceeds to seamlessly explore the array backward, by virtue of set inclusion checks, ensuring we track repeats optimally before they form significant impediments. Ultimately, if no duplicates are stumbled upon, the function returns zero, as no operations are necessary.

Solution Approach

The solution approach is built on utilizing a hash table (set) and reverse traversal of the array nums. Here is the step-by-step breakdown:

Hash Set Utilization: Use a set s to keep track of the elements that have already been traversed. This will help in identifying duplicates efficiently.
Reverse Traversal: Iterate over the array nums in reverse order. This is done because if a duplicate is found, it indicates that all items between this duplicate and the start of the array need to be addressed.
Checking and Removing Duplicates:
- For each element nums[i] starting from the end going towards the start:
  - If nums[i] is found in the set s, it means we've encountered a duplicate.
  - To handle this, calculate the necessary number of operations to remove elements up to this point: (i // 3) + 1. Here, i // 3 gives us how many complete sets of 3 can be removed and adding 1 accounts for any remaining elements that need to be cleared at this point.
Incorporating New Elements: If nums[i] is not in the set, it is added to the set s, and the traversal moves to the next previous element.
Return When Done: If the traversal completes without finding any duplicates, the function simply returns 0 as no operations are needed to make nums distinct.

This methodology efficiently uses the set to track elements and employs the reverse traversal to minimize operations by determining the earliest necessary point to initiate element removal.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach. Consider the integer array:

nums = [4, 1, 2, 4, 3, 2, 5]

Our goal is to make all elements distinct using the minimum number of operations, where each operation involves removing 3 elements from the beginning of the array.

Hash Set Utilization: We initialize an empty set s to keep track of visited elements.
Reverse Traversal: We start examining the array from the last element and move towards the beginning.
- Start with index i = 6 (value 5), it is not in the set, so add 5 to the set. s = {5}.
- Move to index i = 5 (value 2), it is not in the set, so add 2 to the set. s = {5, 2}.
- Move to index i = 4 (value 3), it is not in the set, so add 3 to the set. s = {5, 2, 3}.
- Move to index i = 3 (value 4), it is not in the set, so add 4 to the set. s = {5, 2, 3, 4}.
- Move to index i = 2 (value 2), it is found in the set, indicating a duplicate. Calculate the number of operations required: i // 3 + 1 = 2 // 3 + 1 = 1. After this point, we don't need to check further since the required operation count ensures distinctness.

So, the minimum number of operations needed to ensure all elements in the array are distinct is 1.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumOperations(self, nums: List[int]) -> int:
5        # Create a set to keep track of unique numbers seen so far.
6        unique_numbers = set()
7      
8        # Iterate from the last element towards the first in the list 'nums'.
9        for index in range(len(nums) - 1, -1, -1):
10            # Check if the current number is already in the set of unique numbers.
11            if nums[index] in unique_numbers:
12                # If it is, return the result of integer division of index by 3, plus 1.
13                return index // 3 + 1
14            # Add the current number to the set of unique numbers.
15            unique_numbers.add(nums[index])
16      
17        # If no duplicates found, return 0.
18        return 0
19

1import java.util.HashSet;
2import java.util.Set;
3
4class Solution {
5    public int minimumOperations(int[] nums) {
6        // Initialize a HashSet to keep track of unique elements encountered
7        Set<Integer> uniqueElements = new HashSet<>();
8      
9        // Iterate through the array from the last element to the first
10        for (int i = nums.length - 1; i >= 0; --i) {
11            // Check if the current element is already in the set
12            if (uniqueElements.contains(nums[i])) {
13                // If duplicate found, calculate result based on the index
14                return i / 3 + 1;
15            }
16            // Add the current element to the set
17            uniqueElements.add(nums[i]);
18        }
19      
20        // Return 0 if no duplicates are found
21        return 0;
22    }
23}
24

1#include <vector>
2#include <unordered_set>
3
4class Solution {
5public:
6    // This function calculates the minimum number of operations needed
7    // given a vector of integers.
8    int minimumOperations(std::vector<int>& nums) {
9        std::unordered_set<int> seenNumbers;
10      
11        // Iterate through the vector from the end to the beginning.
12        for (int i = nums.size() - 1; i >= 0; --i) {
13            // Check if the current number has already been seen.
14            if (seenNumbers.find(nums[i]) != seenNumbers.end()) {
15                // Return the calculated operations based on the current index.
16                return i / 3 + 1;
17            }
18            // Insert the current number into the set of seen numbers.
19            seenNumbers.insert(nums[i]);
20        }
21      
22        // If no duplicates are found, return zero.
23        return 0;
24    }
25};
26

1function minimumOperations(nums: number[]): number {
2    // Create a set to store unique numbers that we encounter.
3    const uniqueNumbers = new Set<number>();
4
5    // Traverse the array from the end to the start.
6    for (let index = nums.length - 1; index >= 0; --index) {
7        // Check if the current number is already in the set.
8        if (uniqueNumbers.has(nums[index])) {
9            // If it is, return the minimum number of operations needed
10            // by calculating the ceiling of (current index + 1) divided by 3.
11            return Math.ceil((index + 1) / 3);
12        }
13        // If it's not in the set, add the current number to the set.
14        uniqueNumbers.add(nums[index]);
15    }
16
17    // If no duplicates are found, return 0 operations needed.
18    return 0;
19}
20

Time and Space Complexity

The time complexity of the code is O(n) because the algorithm iterates over the list nums once with a for loop, where n is the length of nums. Each iteration involves operations like checking membership and adding elements to a set, both of which are O(1) on average.

The space complexity is O(n) due to the usage of a set s which, in the worst case scenario, might store all the unique elements in the list nums. This means the space used grows linearly with the number of unique elements.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don’t know