945. Minimum Increment to Make Array Unique

Problem Description

You're handed an array of integers named nums. The task is to make each number in the array unique by performing a certain operation: for any element at index i, where 0 <= i < nums.length, you can increase the value of nums[i] by 1. The goal is to find out the minimum number of such increments needed to ensure that all elements in the array are unique. It is guaranteed that the final answer will be small enough to fit within a 32-bit integer.

Intuition

The intuitive solution involves:

First, sort the array. This ensures that we can process numbers in a sequence and efficiently deal with duplicates.
Then, iterate through the array starting from the second element, comparing each element with the one before it.
If the current element is less than or equal to the previous element, it means we have a duplicate or a possibility of a non-unique value.
To make the current value unique, we need to increment it to be just one more than the previous value. The difference plus one d = nums[i - 1] - nums[i] + 1 gives the exact number of increments needed for that element.
We update the current element to its new unique value and add the number of increments d to a running total, which will eventually be the answer.
Repeat this process for all elements in the array. By the end, the running total gives us the minimum number of moves necessary to achieve uniqueness for all elements in nums.

Learn more about Greedy and Sorting patterns.

Solution Approach

The solution utilizes a simple but effective algorithm which requires minimal data structures – the primary one being the ability to sort the given array. Here's the approach outlined step by step:

Sorting the Array: Start by sorting the nums array. This allows us to process the array in ascending order and handle any duplicates or clusters of the same number effectively.
Initialization: A variable, ans, is initialized to 0. This variable will keep track of the total number of increments we perform across the entire array.
Iterate Through the Array: Iterate through the sorted nums starting from the index 1 to the end of the array. We compare each element with the previous one to check for duplicates or the sequence being out of order.
Processing Each Element:
- For each element at index i, check if it's less than or equal to the element at index i - 1.
- If it is, we need to increment it to make it unique. We calculate the difference + 1 by nums[i - 1] - nums[i] + 1, which tells us how much we need to increment the current element to not only make it unique but also ensure it's greater than the previous element.
- Add this difference to the nums[i] to update the value of the current element, making it unique.
- Also, add this difference to the ans variable, which accumulates the total increments made.
Returning the Answer: After the loop terminates, ans holds the total number of increments needed to make all elements in the array unique. Return ans.

This solution is quite efficient with a time complexity of O(n log n) due to the sort operation. The following loop has a complexity of O(n), but since sorting takes precedence in terms of complexity analysis, it doesn't change the overall time complexity.

The Python code implementation following this algorithm ensures that with minimal space overhead, and in a reasonably optimal time, we arrive at the least number of moves needed to make every element in the array nums unique.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Given an array of integers nums = [3, 2, 1, 2], our task is to make each number in the array unique with the least number of increments.

Following the solution approach, let's walk through the process:

Sorting the Array:
- We start by sorting nums. After sorting, the array becomes nums = [1, 2, 2, 3].
Initialization:
- Next, we initialize the answer variable ans to 0. This variable will count the total increments.
Iterate Through the Array:
- We then iterate through the sorted nums beginning from the index 1.
Processing Each Element:
- At index 1, nums[0] = 1 and nums[1] = 2. Since nums[1] is greater than nums[0], no increment is needed.
- At index 2, we have a duplicate since nums[2] = 2 and nums[1] was also 2. We need to increment nums[2] by 1 to make it unique. So nums[2] becomes 3 and ans is incremented by 1 (total increments so far: 1).
- However, now at index 3, nums[3] = 3 which is equal to nums[2] after the previous increment. So, we need to increment nums[3] until it is unique. The next unique value would be 4, which means we need to increment nums[3] by 1. Now nums[3] becomes 4, and we add 1 to ans making the total increments 2.
Returning the Answer:
- After processing each element, the modified array is nums = [1, 2, 3, 4], and ans = 2. Therefore, the minimum number of increments needed to ensure all elements are unique is 2.

The array modification steps are summarized as follows:

Initial Array: [3, 2, 1, 2]
After Sorting: [1, 2, 2, 3]
Make nums[2] unique: [1, 2, 3, 3] (ans = 1)
Make nums[3] unique: [1, 2, 3, 4] (ans = 2)

Return ans, which is 2. If we apply the same approach to any array using the described algorithm, we will determine the minimum increments necessary to make all elements unique.

Solution Implementation

1class Solution:
2    def minIncrementForUnique(self, nums: List[int]) -> int:
3        # Sort the input list to ensure duplicate or smaller values follow larger values.
4        nums.sort()
5      
6        # Initialize the answer to count the minimum increment required.
7        increments_needed = 0
8      
9        # Iterate through the list starting from the second element.
10        for i in range(1, len(nums)):
11            # If the current number is less than or equal to the previous number,
12            # it's not unique or needs to be incremented to be unique.
13            if nums[i] <= nums[i - 1]:
14                # Calculate the difference needed to make the current number
15                # greater than the previous number by one.
16                diff = nums[i - 1] - nums[i] + 1
17              
18                # Increment the current number by the calculated difference.
19                nums[i] += diff
20              
21                # Add the difference to the increments needed.
22                increments_needed += diff
23              
24        # Return the total number of increments needed to make all numbers unique.
25        return increments_needed
26

1class Solution {
2    public int minIncrementForUnique(int[] nums) {
3        // Sort the input array to make it easier to deal with duplicates
4        Arrays.sort(nums);
5      
6        // Initialize a variable to keep track of the number of increments needed
7        int increments = 0;
8      
9        // Start iterating from the second element (i = 1) since we compare with the previous one
10        for (int i = 1; i < nums.length; ++i) {
11            // If the current element is less than or equal to the previous one, it's not unique
12            if (nums[i] <= nums[i - 1]) {
13                // Calculate the difference needed to make the current element unique
14                int difference = nums[i - 1] - nums[i] + 1;
15              
16                // Increment the current element by the needed difference
17                nums[i] += difference;
18              
19                // Accumulate the total increments needed
20                increments += difference;
21            }
22        }
23      
24        // Return the total number of increments needed for the array to have all unique elements
25        return increments;
26    }
27}
28

1#include <vector>
2#include <algorithm> // Include necessary headers
3
4class Solution {
5public:
6    int minIncrementForUnique(vector<int>& nums) {
7        // Sort the input array to arrange numbers in non-decreasing order.
8        sort(nums.begin(), nums.end());
9      
10        // Initialize the variable to store the minimum increments needed.
11        int minIncrements = 0;
12      
13        // Iterate through the array starting from the second element.
14        for (int i = 1; i < nums.size(); ++i) {
15            // Check if the current element is less than or equal to the previous element.
16            if (nums[i] <= nums[i - 1]) {
17                // Calculate the difference needed to make the current number unique.
18                int difference = nums[i - 1] - nums[i] + 1;
19              
20                // Increment the current number by the calculated difference.
21                nums[i] += difference;
22              
23                // Add the difference to the total number of increments needed.
24                minIncrements += difference;
25            }
26        }
27      
28        // Return the total minimum increments needed to make all the nums unique.
29        return minIncrements;
30    }
31};
32

1// Import array and algorithm functionality
2function sortArray(nums: number[]): number[] {
3    return nums.sort((a, b) => a - b);
4}
5
6function minIncrementForUnique(nums: number[]): number {
7    // Sort the input array to arrange numbers in non-decreasing order.
8    nums = sortArray(nums);
9
10    // Initialize the variable to store the minimum increments needed.
11    let minIncrements: number = 0;
12
13    // Iterate through the array starting from the second element.
14    for (let i = 1; i < nums.length; i++) {
15        // Check if the current element is less than or equal to the previous element.
16        if (nums[i] <= nums[i - 1]) {
17            // Calculate the difference needed to make the current number unique.
18            const difference: number = nums[i - 1] - nums[i] + 1;
19
20            // Increment the current number by the calculated difference.
21            nums[i] += difference;
22
23            // Add the difference to the total number of increments needed.
24            minIncrements += difference;
25        }
26    }
27
28    // Return the total minimum increments needed to make all the numbers unique.
29    return minIncrements;
30}
31

Time and Space Complexity

Time Complexity

The time complexity of the provided code is determined by several factors:

Sorting the input list, which is nums.sort(). This operation is typically implemented using an algorithm like Timsort (in Python's sort function), which has a time complexity of O(n log n) where n is the number of elements in the list.
A single for loop that iterates over the sorted list nums, which adds a time complexity of O(n).

Hence, the total time complexity is dominated by the sorting operation, which gives us:

Time Complexity: O(n log n)

Space Complexity

The space complexity of the provided code is :

No extra space is used apart from the initial input list and a variable ans that keeps track of the increments needed to make each element in the list unique. This results in a constant amount of additional space being used, i.e., O(1).

Space Complexity: O(1)

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: