Minimum Increment to Make Array Unique - Practice Coding Problems

Minimum Increment to Make Array Unique - Problem

You are given an integer array nums. In one move, you can pick an index i where 0 <= i < nums.length and increment nums[i] by 1.

Return the minimum number of moves to make every value in nums unique.

The test cases are generated so that the answer fits in a 32-bit integer.

Input & Output

Example 1 — Basic Duplicates

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

› Output: 1

💡 Note: One of the 2's needs to be incremented to 3. Total moves: 1 (change second 2 to 3).

Example 2 — Multiple Duplicates

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

› Output: 3

💡 Note: After sorting: [1,2,2,2,3,6]. Second 2→3 (1 move), third 2→4 (2 moves). Total: 3 moves.

Example 3 — Already Unique

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

› Output: 0

💡 Note: All elements are already unique, no moves needed.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array with duplicate values that need to be made unique

Process

Sort array and increment duplicates to next available values

Output

Minimum number of increment operations needed

Key Takeaway

🎯 Key Insight: Sort first to group duplicates, then ensure each element is at least previous + 1

Asked in

G Google 15 a Amazon 12 f Meta 8 Apple 6

The optimal approach is to sort the array first, then ensure each element is at least previous + 1. This groups duplicates together and allows us to fix them in a single pass. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n³)	O(1)	For each duplicate, keep incrementing until it becomes unique
Sort First Approach	O(n log n)	O(1)	Sort array first, then ensure each element is at least previous + 1
Counting and Redistribution	O(n + k)	O(k)	Count frequency of each value, then redistribute excess occurrences

Brute Force Simulation — Algorithm Steps

Step 1: Find a duplicate value
Step 2: Increment it until unique
Step 3: Repeat until no duplicates

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Duplicate

Scan array to find first duplicate value

Increment

Keep incrementing until value becomes unique

Repeat

Continue until no duplicates remain

Code -

solution.c — C

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

int solution(int* nums, int size) {
    int moves = 0;
    while (1) {
        // Find first duplicate
        int duplicateIdx = -1;
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (nums[i] == nums[j]) {
                    duplicateIdx = j;
                    break;
                }
            }
            if (duplicateIdx != -1) break;
        }
        
        if (duplicateIdx == -1) break; // No more duplicates
        
        // Increment the duplicate until unique
        while (1) {
            int hasDup = 0;
            for (int i = 0; i < size; i++) {
                if (i != duplicateIdx && nums[i] == nums[duplicateIdx]) {
                    hasDup = 1;
                    break;
                }
            }
            if (!hasDup) break;
            nums[duplicateIdx]++;
            moves++;
        }
    }
    
    return moves;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each duplicate (O(n)), increment until unique (O(n)), check uniqueness (O(n))

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for counting and tracking

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 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