Minimum Number of Operations to Have Distinct Elements Python/Java solution

The typical implementation uses a hash set and a reverse loop. For each element, check if it already exists in the set. If a duplicate is found at index i, return ceil((i + 1) / 3). The same logic translates easily across Python, Java, C++, Go, and TypeScript.

What is the best approach for Minimum Number of Operations to Have Distinct Elements?

The optimal approach uses a hash set with reverse traversal. Scan the array from right to left while inserting elements into a set. The first duplicate encountered indicates the earliest index that must be removed. The number of operations is ceil((i + 1) / 3). This runs in O(n) time with O(n) space.

Is Minimum Number of Operations to Have Distinct Elements asked at Google/Amazon/Meta?

Array and hash table problems with duplicate detection frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that involve prefix removal, deduplication, or set-based checks are common in coding rounds.

What data structure is used in Minimum Number of Operations to Have Distinct Elements?

A hash set is the primary data structure. It allows constant-time checks to determine whether an element has already appeared while scanning the array in reverse.

What is the time complexity of Minimum Number of Operations to Have Distinct Elements?

The optimal solution runs in O(n) time because the array is traversed once from right to left and each hash set lookup is O(1) on average. Space complexity is O(n) due to storing elements in the set to track duplicates.

Description Hints 3 Solution Video 13:04

3779. Minimum Number of Operations to Have Distinct Elements

Q: Is Minimum Number of Operations to Have Distinct Elements easy or hard?

This problem is generally classified as Medium difficulty. The logic becomes straightforward once you realize that simulating operations is unnecessary and that a reverse traversal with a hash set directly reveals the minimum prefix that must be removed.

Q: How to solve Minimum Number of Operations to Have Distinct Elements in O(n)?

Traverse the array from the end while maintaining a hash set of seen values. Insert each element as you move left. When a duplicate appears, record its index i because all elements from 0 to i must be removed. Since each operation removes three elements, compute the answer as ceil((i + 1) / 3).

Medium42.1% acceptance1 company

You are given an integer array nums.

In one operation, you remove the first three elements of the current array. If there are fewer than three elements remaining, all remaining elements are removed.

Repeat this operation until the array is empty or contains no duplicate values.

Return an integer denoting the number of operations required.

Example 1:

Input: nums = [3,8,3,6,5,8]

Output: 1

Explanation:

In the first operation, we remove the first three elements. The remaining elements [6, 5, 8] are all distinct, so we stop. Only one operation is needed.

Example 2:

Input: nums = [2,2]

Output: 1

Explanation:

After one operation, the array becomes empty, which meets the stopping condition.

Example 3:

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

Output: 0

Explanation:

All elements in the array are distinct, therefore no operations are needed.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Asked at 1 company

Accenture

Topics

Array Hash Table

Hints open one at a time

Hint 1

Simulate the operations as described using a map that is initially filled.

Hint 2

While the map does not contain all distinct elements, delete the first three values using a pointer.

Hint 3

Repeat until the map contains all distinct elements or becomes empty.

13:04

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minOperations(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[3,8,3,6,5,8]

Input

[2,2]

Input

[4,3,5,1,2]

Your code is saved on this device.Solution