Minimum Increment to Make Array Unique: Sort and Bump

Given an integer array nums, in one move you can pick an index i and increment nums[i] by 1. Return the minimum number of moves to make every value in nums unique.

This is LeetCode 945: Minimum Increment to Make Array Unique, a medium problem that looks like it might need complicated bookkeeping but simplifies into a clean greedy algorithm once you sort the array first. After sorting, you walk through the values and bump each duplicate forward by just enough to make it unique.

Why this problem matters

Minimum Increment to Make Array Unique is one of the best examples of the "sort first, then greedily fix" pattern. Many problems become much easier once the data is in sorted order, because duplicates and conflicts cluster together. Instead of scanning the whole array to find collisions, you only need to compare each element with its immediate predecessor.

This sort-first greedy pattern shows up in problems like Candy, Jump Game II, and Task Scheduler. Recognizing it lets you collapse what looks like an O(n^2) search into a single O(n) scan after an O(n log n) sort.

The brute force approach

The most natural approach is to repeatedly scan the array for duplicates and increment them until all values are unique.

def min_increment_brute(nums):
    moves = 0
    seen = set()
    for i in range(len(nums)):
        while nums[i] in seen:
            nums[i] += 1
            moves += 1
        seen.add(nums[i])
    return moves

This works, but the inner while loop can run many times for each element. Consider nums = [1, 1, 1, 1]. The first 1 is fine. The second 1 bumps to 2 (1 move). The third 1 bumps to 2, then 3 (2 moves). The fourth 1 bumps through 2, 3, to 4 (3 moves). For n copies of the same value, the total work is O(n^2). On large inputs (up to 10^5 elements), this is too slow. The problem is that each element does not know where the "next available slot" is, so it has to search for it one step at a time.

The key insight: sort then bump forward

Once the array is sorted, duplicates sit next to each other. You can walk through the sorted array with a single variable tracking the previous value. Whenever the current element is not strictly greater than the previous one, you know exactly how far to bump it: set it to prev + 1. The cost of that bump is (prev + 1) - nums[i], and you add it to the total.

Walking through it step by step

Let's trace through nums = [3, 2, 1, 2, 1, 7]. After sorting, we get [1, 1, 2, 2, 3, 7]. The answer is 6 moves, producing [1, 2, 3, 4, 5, 7].

Notice how each bump pushes the "previous" value forward, creating a cascade. The element 3 at index 4 had no duplicates in the original array, but by the time we reach it, the running maximum is already 4, so it still needs a bump. This is why sorting is essential: it guarantees that every conflict is caught in a single left-to-right pass.

The greedy solution

def minIncrementForUnique(nums):
    nums.sort()
    moves = 0
    for i in range(1, len(nums)):
        if nums[i] <= nums[i - 1]:
            target = nums[i - 1] + 1
            moves += target - nums[i]
            nums[i] = target
    return moves

Three lines of logic inside the loop. Here is what each piece does:

1. Sort the array. This clusters duplicates together and lets us process conflicts in order.
2. Walk from index 1 to the end. For each element, check if it is less than or equal to the previous element.
3. Bump it up to nums[i - 1] + 1 if there is a conflict. The cost is target - nums[i], which is the number of increments needed.
4. Accumulate the cost in moves and update nums[i] to the new value so subsequent comparisons use the bumped value.

The if nums[i] <= nums[i - 1] check catches both duplicates (equal values) and cases where the previous element was already bumped past the current one.

Complexity analysis

The scan after sorting is O(n), so the total time is governed by the sort. This is a significant improvement over the O(n^2) brute force. You need to inspect every element at least once, and you need sorted order, so O(n log n) is optimal for a comparison-based approach.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Sort-first greedy

The pattern of sorting the input first so that a single linear scan can resolve all conflicts:

data.sort()
state = initial_value
for i in range(1, len(data)):
    if conflict(data[i], state):
        fix(data[i], state)
    state = update(data[i])

In Minimum Increment to Make Array Unique, the state is the previous value and the conflict is nums[i] <= prev. In Merge Intervals, the state is the current merged interval and the conflict is overlap. In Non-overlapping Intervals, the state is the end of the last kept interval. The skeleton is identical: sort, then scan, then fix.

2. Running maximum tracking

The pattern of maintaining a running maximum (or "next available slot") as you process elements:

prev = data[0]
for i in range(1, len(data)):
    if data[i] <= prev:
        data[i] = prev + 1
    prev = data[i]

The variable prev acts as a running maximum. It only ever increases. Every new element either exceeds it (no conflict) or gets pushed just past it (resolving the conflict). This is a simplified form of the "greedy forward scan" where you track the frontier and push items forward as needed.

Edge cases

Before submitting, make sure your solution handles these:

• All identical values [3, 3, 3, 3]: after sorting, each element bumps to the next integer. Result is [3, 4, 5, 6]. Moves = 0 + 1 + 2 + 3 = 6.
• Already unique and sorted [1, 2, 3, 4]: no conflicts, no bumps. Moves = 0.
• Already unique but unsorted [4, 2, 1, 3]: after sorting, [1, 2, 3, 4]. No conflicts. Moves = 0.
• Two elements, same value [5, 5]: second element bumps to 6. Moves = 1.
• Single element [7]: the loop does not execute. Moves = 0.
• Large gaps between clusters [1, 1, 1, 100, 100, 100]: the first cluster becomes [1, 2, 3] (3 moves), the second becomes [100, 101, 102] (3 moves). Total = 6. Gaps between clusters do not cause cascading.

The greedy solution handles all of these without special-case logic.

Common mistakes

1. Forgetting to sort first. Without sorting, you cannot guarantee that a single left-to-right pass catches all conflicts. You might bump an element to a value that collides with something later in the array.

2. Using < instead of <= in the comparison. The condition must be nums[i] <= nums[i - 1], not nums[i] < nums[i - 1]. Equal values are duplicates and need to be bumped. Using strict less-than misses the case where two adjacent sorted elements are equal.

3. Not updating the array element after bumping. If you calculate the cost but forget to set nums[i] = target, subsequent comparisons use the old value. This causes the running maximum to fall behind, and you miss cascading conflicts.

4. Trying to decrement instead of increment. The problem only allows incrementing. You cannot move an element down to fill a gap below it. The greedy approach works precisely because it pushes elements forward, never backward.

From understanding to recall

You have read the sort-and-bump solution and it makes sense. Sort, walk, bump, count. Four steps. But can you write it from scratch in an interview without looking at it?

The details matter: using <= not <, computing target = nums[i - 1] + 1, adding target - nums[i] to moves, and updating nums[i] = target. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the sort-first greedy loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "make values unique with minimum cost" and the code flows out without hesitation.

The sort-first greedy pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Lemonade Change - Greedy decision-making with limited resources
• Gas Station - Greedy with running sums
• Sort Colors - In-place array rearrangement

CodeBricks breaks the minimum increment to make array unique LeetCode problem into its sort-first greedy and running maximum tracking building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a sort-and-bump question shows up in your interview, you do not think about it. You just write it.