Minimum Number of Operations to Make Elements in Array Distinct

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

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: An empty array is considered to have distinct elements.

Return the minimum number of operations needed to make the elements in the array distinct.

Input & Output

Example 1 — Duplicate Elements

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

› Output: 1

💡 Note: Elements 1 appears twice. Remove first 3 elements [1,2,1], leaving [3,4] which are distinct. One operation needed.

Example 2 — Already Distinct

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

› Output: 0

💡 Note: All elements are already distinct, so no operations needed.

Example 3 — Small Array with Duplicates

$ Input: nums = [1,1]

› Output: 1

💡 Note: Two duplicate 1s. Since array has less than 3 elements, remove all in one operation.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with duplicate elements that need to be eliminated

Remove Operations

Remove 3 elements at a time from the beginning until distinct

Result

Return minimum operations needed

Key Takeaway

🎯 Key Insight: Work backwards to find the rightmost duplicate, then calculate how many 3-element removals are needed

Asked in

f Meta 8 G Google 6 a Amazon 4

The key insight is to work backwards from the end of the array to find the rightmost position where all elements to the right are distinct. The optimal approach uses a hash map in O(n) time to scan right-to-left, stopping at the first duplicate found. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n²)	O(n)	Simulate removing 3 elements at a time until array becomes distinct
Hash Map Optimization	O(n)	O(n)	Use hash map to track element positions and find optimal cutting point

Brute Force Simulation — Algorithm Steps

Step 1: Check if current array has all distinct elements
Step 2: If not, remove first 3 elements (or all if less than 3)
Step 3: Increment operation count and repeat

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Array

Look for duplicate elements

Remove Elements

Take 3 from front if duplicates exist

Repeat

Continue until all elements distinct

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* nums, int size) {
    int operations = 0;
    int start = 0;
    
    while (start < size) {
        // Check if remaining elements are distinct
        bool seen[200001] = {false}; // Assuming values in reasonable range
        bool isDistinct = true;
        
        for (int i = start; i < size; i++) {
            int val = nums[i] + 100000; // Offset for negative numbers
            if (seen[val]) {
                isDistinct = false;
                break;
            }
            seen[val] = true;
        }
        
        if (isDistinct) {
            break;
        }
        
        // Remove 3 elements from beginning (or all remaining)
        if (size - start <= 3) {
            start = size;
        } else {
            start += 3;
        }
        operations++;
    }
    
    return operations;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int nums[10000];
    int size = 0;
    
    if (strlen(line) > 3) {
        char* token = strtok(line + 1, ",]");
        while (token != NULL) {
            nums[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n/3 operations, we check all remaining elements for duplicates

⚠ Quadratic Growth

Space Complexity

O(n)

Hash set to check for duplicates in remaining array

⚡ Linearithmic Space

12.4K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler