#945

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Increment to Make Array Unique

This problem challenges you to find the minimum moves to make all elements in an array unique by incrementing elements.

Problem Statement

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. The goal is to return the minimum number of moves required to make every value in the array unique.

For example, for an input array nums = [1,2,2], after 1 move, the array becomes [1,2,3], ensuring uniqueness. The test cases are designed such that the result fits within a 32-bit integer.

Examples

Example 1

Input: nums = [1,2,2]

Output: 1

After 1 move, the array could be [1, 2, 3].

Example 2

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

Output: 6

After 6 moves, the array could be [3, 4, 1, 2, 5, 7]. It can be shown that it is impossible for the array to have all unique values with 5 or less moves.

Constraints

1 <= nums.length <= 105
0 <= nums[i] <= 105

Solution Approach

Sorting and Greedy Increment

First, sort the array. Then, traverse the array, and for each number, if it's not unique (i.e., it's equal to the previous number), increment it until it becomes unique. This greedy strategy ensures that the number of moves is minimized.

Use of Set to Track Uniqueness

After sorting the array, maintain a set to track already used numbers. For each number, if it's already in the set, increment it until it’s not found in the set, ensuring uniqueness with the least number of increments.

Efficient Validation of Moves

Once a move is made, check if the new value is valid by verifying it doesn’t conflict with any previously processed values. This ensures that we make the smallest possible increments while ensuring the array’s uniqueness.

Complexity Analysis

Metric	Value
Time	O(n+max)
Space	O(n+max)

The time complexity is O(n + max), where n is the size of the array and max is the largest number in the array. Sorting the array takes O(n log n), while the greedy traversal takes O(n) with additional space for the set to track uniqueness. The space complexity is O(n + max) due to the space needed for the array and set.

What Interviewers Usually Probe

Assess the candidate's understanding of greedy algorithms and sorting strategies.
Test if the candidate can efficiently track uniqueness in large arrays.
Evaluate the candidate’s ability to implement efficient validation methods with minimal operations.

Common Pitfalls or Variants

Common pitfalls

Not sorting the array before applying the greedy strategy.
Failing to validate uniqueness efficiently, leading to redundant checks or incorrect results.
Incorrectly handling edge cases, such as when no increments are needed or when the array has duplicate values at the start.

Follow-up variants

What if you needed to make the array unique by using both increments and decrements? How would the solution change?
If the array could contain negative numbers, how would you modify the approach to ensure uniqueness?
How would you approach this problem if you had to minimize both the number of moves and the final array sum?

FAQ

How do I approach the Minimum Increment to Make Array Unique problem?

Start by sorting the array. Then, increment each element as needed to ensure uniqueness, using a greedy strategy and tracking used values with a set.

What is the time complexity of solving the Minimum Increment to Make Array Unique problem?

The time complexity is O(n log n) due to the sorting step, followed by an O(n) greedy traversal. Space complexity is O(n + max), where max is the largest number in the array.

Can the Minimum Increment to Make Array Unique problem be solved without sorting?

Sorting is an essential part of the solution as it ensures that we can increment values in the smallest possible order, minimizing the total number of moves.

What are some common pitfalls in solving the Minimum Increment to Make Array Unique problem?

Key pitfalls include failing to sort the array first, inefficiently validating uniqueness, or not handling edge cases where no increments are needed.

How does the greedy approach apply to the Minimum Increment to Make Array Unique problem?

The greedy approach ensures that each element is incremented to the smallest possible value that maintains uniqueness, minimizing the total number of moves required.

terminal

Solution

Solution 1: Sorting + Greedy

First, we sort the array $\textit{nums}$, and use a variable $\textit{y}$ to record the current maximum value, initially $\textit{y} = -1$.

1

2

3

4

5

6

7

8

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort()
        ans, y = 0, -1
        for x in nums:
            y = max(y + 1, x)
            ans += y - x
        return ans

Solution 2: Counting + Greedy

According to the problem description, the maximum value of the result array $m = \max(\textit{nums}) + \textit{len}(\textit{nums})$. We can use a counting array $\textit{cnt}$ to record the occurrence count of each element.

1

2

3

4

5

6

7

8

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort()
        ans, y = 0, -1
        for x in nums:
            y = max(y + 1, x)
            ans += y - x
        return ans

Continue Practicing

#1054 distant barcodes #1090 largest values from labels #621 task scheduler