Jobs

Interviews

Discussions

Minimum Increment to Make Array Unique

Medium

Coursera

4 views

Topics:

ArraysGreedy Algorithms

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.

Return the minimum number of moves to make every value in nums unique.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: nums = [1,2,2]
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].

Example 2:

Input: nums = [3,2,1,2,1,7]
Output: 6
Explanation: 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 <= 10⁵
0 <= nums[i] <= 10⁵

Try coding it in LeetCode

Minimum Increment to Make Array Unique

Medium

Coursera

4 views

Topics:

ArraysGreedy Algorithms

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.

Return the minimum number of moves to make every value in nums unique.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: nums = [1,2,2]
Output: 1
Explanation: After 1 move, the array could be [1, 2, 3].

Example 2:

Input: nums = [3,2,1,2,1,7]
Output: 6
Explanation: 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 <= 10⁵
0 <= nums[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within the input array `nums`? Can they be negative, zero, or only positive?
What is the maximum size of the input array `nums`? This will help me understand any potential memory or performance bottlenecks.
If the input array is already unique, should I return 0?
Are we guaranteed that it's always possible to make the array unique through incrementing elements?
Is the order of elements in the output important, or can the array be considered unordered after making elements unique?

Brute Force Solution

Approach

The brute force method for making all numbers in a list unique involves checking every possible increase we can make to the numbers. We try small adjustments and see if that fixes the problem; if not, we try bigger ones until all numbers are distinct.

Here's how the algorithm would work step-by-step:

Start by looking at the first number in the list. Then, look at the second number.
If the second number is the same as the first, increase the second number by one.
Keep checking if the second number is now different from all the numbers before it. If it is still the same as one of the previous numbers, increase it again.
Repeat the increasing process until the second number is unique (different from all earlier numbers).
Move on to the third number. Compare it to the first and second numbers.
Increase the third number until it's different from all the numbers that came before it.
Continue this process for every number in the list. For each number, compare it to all the previous numbers and increase it until it is unique.
Keep track of how much you increased each number. At the end, add up all the increases to find the total increase needed.

Code Implementation

def min_increment_for_unique(numbers):
    total_increments = 0
    for current_index in range(1, len(numbers)):
        while True:
            # Check against all previous numbers for uniqueness
            is_unique = True
            for previous_index in range(current_index):
                if numbers[current_index] == numbers[previous_index]:
                    is_unique = False
                    break

            if is_unique:
                break

            # Increment current number if not unique
            numbers[current_index] += 1
            total_increments += 1

    return total_increments

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input array. For each element, it compares it with all the preceding elements to ensure uniqueness. In the worst case, for each of the n elements, it might perform up to n-1 comparisons and increments. This results in a nested loop-like behavior where, approximately, n elements are compared with up to n other elements, leading to a total of roughly n * (n-1) operations. This simplifies to O(n²).

Space Complexity

O(1) – The brute force method described only uses a few integer variables to store the current number being considered, the index of previous numbers, and the running total of increments. The space required for these variables does not scale with the input array size N. Thus the auxiliary space complexity is constant.

Optimal Solution

Approach

To minimize increases, we need to think about grouping similar numbers together. The best way is to sort the numbers first, then we only need to increase a number if it's less than or equal to the number that came before it. We will increase the number until it is just one bigger than the previous number.

Here's how the algorithm would work step-by-step:

First, put all the numbers in order from smallest to largest.
Now, go through the numbers one by one.
If a number is the same as or smaller than the number before it, we need to make it bigger.
Increase the number to be just one more than the previous number.
Keep track of how much we increased the number by.
The total amount we increased all the numbers is the answer.

Code Implementation

def minimum_increment_to_make_array_unique(numbers):
    numbers.sort()

    moves_needed = 0
    previous_number = -1

    for index in range(len(numbers)): 
        current_number = numbers[index]

        # If the current number is less than or equal to
        # the previous, we need to increment it.
        if current_number <= previous_number:
            moves_needed += previous_number - current_number + 1
            numbers[index] = previous_number + 1

        previous_number = numbers[index]

    return moves_needed

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this algorithm is sorting the input array of size n. Sorting algorithms like merge sort or quicksort, commonly used in standard libraries, have a time complexity of O(n log n). The subsequent linear scan through the sorted array to adjust values and count increments takes O(n) time. Since O(n log n) grows faster than O(n), the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(1) – The algorithm sorts the input array in place, meaning it doesn't use any additional space that scales with the input size N. It only uses a few variables like `prev` to keep track of the previous element, and `moves` to count the increments. Since the extra space required is independent of the number of elements in the input array, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no increments are needed for an empty array.
Array with a single element	Return 0 as a single element is inherently unique.
Array with all identical elements	The algorithm should correctly increment these elements to achieve uniqueness.
Array with a large range of values, potentially leading to large increments	Sorting and incrementing to the next available value will still work correctly, but consider potential integer overflow if the increments become excessively large.
Array with negative numbers	The algorithm, if based on sorting and incrementing to next available element, should work correctly with negative numbers; the core logic isn't affected.
Array with a few extremely large values and many small values	Sorting ensures the large values are handled last, avoiding unnecessary increments to smaller values that might later require even larger increments.
Integer overflow when calculating the total increments	Use a 64-bit integer type (long in Java/C++, or appropriate type in Python) to store the sum of increments.
Array is already unique	The algorithm should correctly return 0 as no increments are required.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within the input array `nums`? Can they be negative, zero, or only positive?
What is the maximum size of the input array `nums`? This will help me understand any potential memory or performance bottlenecks.
If the input array is already unique, should I return 0?
Are we guaranteed that it's always possible to make the array unique through incrementing elements?
Is the order of elements in the output important, or can the array be considered unordered after making elements unique?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first number in the list. Then, look at the second number.
If the second number is the same as the first, increase the second number by one.
Keep checking if the second number is now different from all the numbers before it. If it is still the same as one of the previous numbers, increase it again.
Repeat the increasing process until the second number is unique (different from all earlier numbers).
Move on to the third number. Compare it to the first and second numbers.
Increase the third number until it's different from all the numbers that came before it.
Continue this process for every number in the list. For each number, compare it to all the previous numbers and increase it until it is unique.
Keep track of how much you increased each number. At the end, add up all the increases to find the total increase needed.

Code Implementation

def min_increment_for_unique(numbers):
    total_increments = 0
    for current_index in range(1, len(numbers)):
        while True:
            # Check against all previous numbers for uniqueness
            is_unique = True
            for previous_index in range(current_index):
                if numbers[current_index] == numbers[previous_index]:
                    is_unique = False
                    break

            if is_unique:
                break

            # Increment current number if not unique
            numbers[current_index] += 1
            total_increments += 1

    return total_increments

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, put all the numbers in order from smallest to largest.
Now, go through the numbers one by one.
If a number is the same as or smaller than the number before it, we need to make it bigger.
Increase the number to be just one more than the previous number.
Keep track of how much we increased the number by.
The total amount we increased all the numbers is the answer.

Code Implementation

def minimum_increment_to_make_array_unique(numbers):
    numbers.sort()

    moves_needed = 0
    previous_number = -1

    for index in range(len(numbers)): 
        current_number = numbers[index]

        # If the current number is less than or equal to
        # the previous, we need to increment it.
        if current_number <= previous_number:
            moves_needed += previous_number - current_number + 1
            numbers[index] = previous_number + 1

        previous_number = numbers[index]

    return moves_needed

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no increments are needed for an empty array.
Array with a single element	Return 0 as a single element is inherently unique.
Array with all identical elements	The algorithm should correctly increment these elements to achieve uniqueness.
Array with a large range of values, potentially leading to large increments	Sorting and incrementing to the next available value will still work correctly, but consider potential integer overflow if the increments become excessively large.
Array with negative numbers	The algorithm, if based on sorting and incrementing to next available element, should work correctly with negative numbers; the core logic isn't affected.
Array with a few extremely large values and many small values	Sorting ensures the large values are handled last, avoiding unnecessary increments to smaller values that might later require even larger increments.
Integer overflow when calculating the total increments	Use a 64-bit integer type (long in Java/C++, or appropriate type in Python) to store the sum of increments.
Array is already unique	The algorithm should correctly return 0 as no increments are required.