LeetCode 945 - Minimum Increment to Make Array Unique

LeetCode Problem 945

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Counting

Solution

Problem Understanding

This problem asks us to take an integer array nums and perform a series of increment operations so that every element in the array becomes unique. An increment operation increases an element by exactly 1. The goal is to compute the minimum number of such moves required.

In simpler terms, we are asked: given an array where duplicates may exist, how do we adjust the duplicates with the fewest total increments so that no two elements are the same? The output is a single integer representing this minimum number of moves.

The input array can have up to 100,000 elements, and values range from 0 to 100,000. This implies that brute-force solutions which repeatedly search for the next available number could be too slow. Important edge cases include arrays that are already unique, arrays with all identical elements, arrays containing zeros, or arrays with very large numbers close to 100,000. The problem guarantees that a solution exists that fits within a 32-bit integer.

Approaches

The brute-force approach is straightforward but inefficient. For each element in the array, we could check if it has already appeared in the array or a set. If it has, we increment it by one and repeat this check until we find a number that is unique. We accumulate all increments. This approach is correct because it enforces uniqueness at every step, but it is too slow for large arrays because in the worst case we could perform O(n^2) operations.

The optimal approach relies on sorting the array first. Once the array is sorted, duplicates are adjacent. We can then iterate through the sorted array and ensure that each element is at least one greater than the previous element. If it is not, we calculate the number of increments needed and adjust the current element. This works because sorting ensures that all duplicates are contiguous, so we only need to consider the previous element to maintain uniqueness. This approach is much faster and reduces the problem to linear traversal after sorting.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Increment elements until unique using a set; inefficient for large arrays
Optimal	O(n log n)	O(1)	Sort array and adjust duplicates in one pass; scalable to large arrays

Algorithm Walkthrough

1. Sort the array nums. Sorting ensures that duplicates appear consecutively, which makes it easy to handle conflicts efficiently.
2. Initialize a variable moves to 0 to track the total number of increments.
3. Iterate through the sorted array starting from the second element. For each element, check if it is less than or equal to the previous element.
4. If the current element is less than or equal to the previous element, calculate the difference prev + 1 - current to determine how many increments are required to make it unique.
5. Add the required increments to moves.
6. Update the current element to prev + 1, ensuring that it is now strictly greater than the previous element.
7. Continue until all elements have been processed.
8. Return the total moves.

Why it works: By sorting, duplicates are contiguous. By ensuring each element is at least one greater than its predecessor, we guarantee all elements are unique with minimal increments. Adjusting in-place and counting increments ensures optimal moves without unnecessary operations.

Python Solution

from typing import List

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        nums.sort()
        moves = 0
        
        for i in range(1, len(nums)):
            if nums[i] <= nums[i - 1]:
                increment = nums[i - 1] + 1 - nums[i]
                moves += increment
                nums[i] = nums[i - 1] + 1
        
        return moves

This Python implementation first sorts the array. It then iterates through each element, checking if it is less than or equal to the previous one. If so, it calculates the exact number of increments needed, updates the moves counter, and adjusts the current element to be unique. The use of nums[i - 1] + 1 ensures minimal adjustments while maintaining uniqueness.

Go Solution

import "sort"

func minIncrementForUnique(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    sort.Ints(nums)
    moves := 0

    for i := 1; i < len(nums); i++ {
        if nums[i] <= nums[i-1] {
            increment := nums[i-1] + 1 - nums[i]
            moves += increment
            nums[i] = nums[i-1] + 1
        }
    }

    return moves
}

In Go, the implementation mirrors the Python version. Sorting is done with sort.Ints. Edge cases like empty slices are handled explicitly. Since Go does not have dynamic lists like Python, all operations are performed in-place on the input slice.

Worked Examples

Example 1: nums = [1, 2, 2]

After sorting: [1, 2, 2]

Iteration:

i	nums[i-1]	nums[i]	increment	moves	updated nums
1	1	2	0	0	[1, 2, 2]
2	2	2	1	1	[1, 2, 3]

Return 1.

Example 2: nums = [3, 2, 1, 2, 1, 7]

After sorting: [1, 1, 2, 2, 3, 7]

Iteration:

i	nums[i-1]	nums[i]	increment	moves	updated nums
1	1	1	1	1	[1, 2, 2, 2, 3, 7]
2	2	2	1	2	[1, 2, 3, 2, 3, 7]
3	3	2	2	4	[1, 2, 3, 4, 3, 7]
4	4	3	2	6	[1, 2, 3, 4, 5, 7]
5	5	7	0	6	[1, 2, 3, 4, 5, 7]

Return 6.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates; traversal is O(n)
Space	O(1)	Adjustments are done in-place; only a constant number of extra variables

The sorting step ensures that duplicate handling is linear after the sort. No additional data structures are needed beyond a few counters, giving O(1) space.

Test Cases

# Provided examples
assert Solution().minIncrementForUnique([1,2,2]) == 1  # simple duplicate
assert Solution().minIncrementForUnique([3,2,1,2,1,7]) == 6  # multiple duplicates

# Edge cases
assert Solution().minIncrementForUnique([]) == 0  # empty array
assert Solution().minIncrementForUnique([0]) == 0  # single element
assert Solution().minIncrementForUnique([1,1,1,1]) == 6  # all identical
assert Solution().minIncrementForUnique([0,0,0,0,0]) == 10  # all zeros
assert Solution().minIncrementForUnique([1,2,3,4,5]) == 0  # already unique
assert Solution().minIncrementForUnique([100000,100000,100000]) == 3  # large numbers

Test	Why
[1,2,2]	Basic duplicate handling
[3,2,1,2,1,7]	Multiple duplicates in unordered array
[]	Empty input should return 0
[0]	Single element is trivially unique
[1,1,1,1]	All duplicates, checks cumulative increment calculation
[0,0,0,0,0]	All zeros, checks handling of small numbers
[1,2,3,4,5]	Already unique, no moves needed
[100000,100000,100000]	Edge of value constraints, ensures no overflow

Edge Cases

The first edge case is an empty array. A naive implementation that does not check for length may fail. The correct handling is to return 0 immediately because no moves are required.

The second edge case is an array where all elements are identical. This stresses the increment calculation, as each subsequent element requires more increments than the previous. The algorithm correctly accumulates the moves and adjusts each element incrementally.

The third edge case is arrays containing the maximum allowed value, such as 100,000. Incrementing such numbers could overflow if not handled carefully in languages with fixed integer sizes. In Python