• Leetcode POTDs

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

Problem Statement

Link - Problem 3396

Question

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.

Example 1:

Example 2:

Example 3:

Constraints:

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

Solution

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        vector<bool> seen(101);
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (seen[nums[i]]) {
                return i / 3 + 1;
            }
            seen[nums[i]] = true;
        }
        return 0;
    }
};

Complexity Analysis

| Algorithm     | Time Complexity | Space Complexity |
| ------------- | --------------- | ---------------- |
| Linear Search | O(n)            | O(1)             |

Explanation

Intial Thoughts

To approach this problem, we should first consider the constraints and the allowed operation. We can remove 3 elements from the beginning of the array at a time. Thinking about the problem in reverse might be helpful, as we can start from the end and work our way backward, keeping track of the elements we’ve seen so far. We should also note that an empty array is considered to have distinct elements, which could be a base case for our solution. Breaking down the problem into smaller sub-problems and considering the worst-case scenario could provide more insight. Lastly, thinking about how to utilize the given constraints to minimize the number of operations will be key.

Intuitive Analysis

Intuitively, we can think of this problem as trying to find the minimum number of ‘blocks’ of 3 elements that need to be removed from the beginning of the array to make the remaining elements distinct. We can use a ‘seen’ array to keep track of the elements we’ve encountered so far, similar to how we might use a map to keep track of unique elements in other problems. Starting from the end of the array and moving backward allows us to take advantage of the fact that we can remove elements in ‘blocks’ of 3. By using this approach, we can ensure that we’re removing the minimum number of elements necessary to make the remaining elements distinct. Additionally, thinking about the problem in terms of ‘removing blocks’ rather than individual elements can help simplify the solution and make it more efficient.

1. Intuition

• The problem requires finding the minimum number of operations to make the elements in the array distinct by removing 3 elements from the beginning of the array.
• To approach this problem, we need to think about how to efficiently check for duplicate elements in the array.
• We can start from the end of the array and move backwards, keeping track of the elements we have seen so far.
• The key insight is that as soon as we encounter a duplicate element, we know that we need to remove all elements before it to make the array distinct.
• This is because removing 3 elements from the beginning of the array is the only operation allowed, so we need to find the first duplicate element from the end of the array.
• By using a boolean array seen to keep track of the elements we have seen, we can efficiently check for duplicates and find the minimum number of operations needed.
• The time complexity of this approach is O(n), where n is the length of the array, and the space complexity is O(1) since we only use a fixed-size boolean array.

2. Implementation

• We start by initializing a boolean array seen of size 101 to keep track of the elements we have seen, with all elements initially set to false.
• We then iterate over the array from the end to the beginning, checking if the current element nums[i] has been seen before by checking the value of seen[nums[i]].
• If seen[nums[i]] is true, it means we have encountered a duplicate element, so we return the index i divided by 3 plus 1, which represents the minimum number of operations needed.
• If seen[nums[i]] is false, we set it to true to mark the element as seen and continue iterating over the array.
• If we finish iterating over the array without finding any duplicates, we return 0, indicating that the array already contains distinct elements.
• The return i / 3 + 1 statement calculates the minimum number of operations needed by dividing the index i by 3 and rounding up to the nearest integer, which represents the number of times we need to remove 3 elements from the beginning of the array.
• The seen[nums[i]] = true statement marks the current element as seen, allowing us to efficiently check for duplicates in the array.

Complexity Analysis

Time Complexity:

• The time complexity of the given code can be analyzed by considering the for loop that iterates through the nums vector, resulting in a linear time complexity of O(n), where n is the size of the input vector nums. In the worst, average, and best cases, the algorithm must potentially check every element in the vector, thus the time complexity remains O(n).
• The dominant operation in this algorithm is the iteration through the vector using for (int i = nums.size() - 1; i >= 0; i--), which has a direct impact on the time complexity.
• Justification of the Big O classification can be mathematically reasoned as the time taken grows linearly with the size of the input vector nums, hence O(n).

Space Complexity:

• The space complexity of the algorithm is determined by the additional memory used, which in this case is the seen vector of size 101, hence the space complexity is O(1) as it does not grow with the size of the input vector nums.
• The seen vector has a constant size and does not depend on the input size n, thus it does not affect the overall space complexity.
• Justification of the space complexity can be reasoned as the algorithm uses a constant amount of space to store the seen vector, regardless of the input size, resulting in O(1) space complexity.

Footnote

This question is rated as Easy difficulty.

Hints

The constraints are small. Try brute force.

Similar Questions: