945. Minimum Increment to Make Array Unique

MediumGreedyArrayCountingSorting
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

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

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

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:

  1. Sorting the Array:

    • We start by sorting nums. After sorting, the array becomes nums = [1, 2, 2, 3].

  2. Initialization:

    • Next, we initialize the answer variable ans to 0. This variable will count the total increments.

  3. Iterate Through the Array:

    • We then iterate through the sorted nums beginning from the index 1.

  4. 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.

  5. 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
Not Sure What to Study? Take the 2-min Quiz：

How many times is a tree node visited in a depth first search?

Time and Space Complexity

Time Complexity

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

  1. 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.

  2. 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 :

  1. 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.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫