Minimum Number of Operations to Make Elements in Array Distinct
Minimum Number of Operations to Make Elements in Array Distinct solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Number of Operations to Make Elements in Array Distinct is an easy coding problem on arrays and hash table, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums. You want every element of the array to be distinct.
The only operation allowed removes the first three elements of the array; if fewer than three remain, it removes all of them. An empty array counts as distinct.
Return the minimum number of operations needed to make the elements distinct.
Example 1
Input: nums = [3,8,3,5,1,1,9]
Output: 2
Explanation: After one operation `[5,1,1,9]` still repeats `1`; after the second only `[9]` is left.
Example 2
Input: nums = [4,5,6,4,4]
Output: 2
Explanation: One operation leaves `[4,4]`; the second empties the array.
Example 3
Input: nums = [2,9,4]
Output: 0
Explanation: The elements are already distinct.
Constraints
1 <= nums.length <= 1001 <= nums[i] <= 100
Hints for Minimum Number of Operations to Make Elements in Array Distinct
Hint 1
The operations always remove a prefix, so what remains is a suffix of
numsstarting at a multiple of 3.Hint 2
Find the shortest suffix that is already distinct: scan from the right and stop at the first value you have seen before.
Hint 3
If that repeated value sits at index
i, the removed prefix must cover indexi, which takesfloor(i / 3) + 1operations.
How to solve Minimum Number of Operations to Make Elements in Array Distinct
After t operations the array is the suffix starting at 3t. A suffix is distinct exactly when it starts after the last index i whose value occurs again to its right, so the answer is the smallest t with 3t > i.
Approach
- Walk
numsfrom right to left, marking values in a seen table. - At the first index
iwhose value is already marked, returni / 3 + 1(integer division). - If the walk finishes without a repeat, return
0.
Why it works
The suffix starting at i + 1 is distinct (the scan found no repeat there), and any suffix starting at or before i contains nums[i] and its later copy. So the remaining suffix must start beyond i; the first multiple of 3 greater than i is 3 * (floor(i / 3) + 1).
Complexity
- Time —
O(n) - Space —
O(V) with V = 100 possible values
Pitfalls
- Scanning from the left finds the first duplicate pair, not the last repeated index that matters.
- An operation on fewer than three elements still counts as one operation.
Reference solution
Python
from typing import List
def minimumOperations(nums: List[int]) -> int:
seen = set()
for i in range(len(nums) - 1, -1, -1):
if nums[i] in seen:
return i // 3 + 1
seen.add(nums[i])
return 0Java
public static int minimumOperations(int[] nums) {
boolean[] seen = new boolean[101];
for (int i = nums.length - 1; i >= 0; i--) {
if (seen[nums[i]]) return i / 3 + 1;
seen[nums[i]] = true;
}
return 0;
}C++
int minimumOperations(vector<int>& nums) {
vector<bool> seen(101, false);
for (int i = (int)nums.size() - 1; i >= 0; i--) {
if (seen[nums[i]]) return i / 3 + 1;
seen[nums[i]] = true;
}
return 0;
}JavaScript
var minimumOperations = function(nums) {
var seen = new Array(101).fill(false);
for (var i = nums.length - 1; i >= 0; i--) {
if (seen[nums[i]]) return Math.floor(i / 3) + 1;
seen[nums[i]] = true;
}
return 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets