We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Increment to Make Array Unique

Number: 982

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Bloomberg, TikTok, PayPal, Microsoft, Coursera

Problem Description

Given an array of integers, the goal is to calculate the minimum number of moves required to make all elements in the array unique. A single move consists of incrementing any element by 1.

Key Insights

  • Sorting the array helps group duplicates together.
  • After sorting, for each element if it is not greater than the previously updated element, it must be increased to be one more than the previous element.
  • The approach is greedy: always use the smallest possible increment to resolve duplicates.
  • Maintaining the sorted order ensures the solution remains optimal.

Space and Time Complexity

Time Complexity: O(n log n) due to the sort operation, where n is the number of elements in the array. Space Complexity: O(1) extra space if the sorting is done in place (or O(n) if additional space is needed for the sorting algorithm).

Solution

The algorithm starts by sorting the array to ensure duplicate values are adjacent. Then, by iterating through the array (starting from the second element), we check if the current element is less than or equal to the previous element. If so, we calculate the increment needed to ensure the current element becomes one more than the previous element, keeping a tally of the moves required. This greedy approach minimizes the total number of increments required while ensuring all numbers are unique.

Code Solutions

def minIncrementForUnique(nums):
    # Sort the array so that duplicate numbers are next to each other
    nums.sort()
    moves = 0
    # Iterate through the array from the second element onward
    for i in range(1, len(nums)):
        # If the current number is not greater than the previous number
        if nums[i] <= nums[i - 1]:
            # Calculate the required increment to make it one more than the previous number
            increment = nums[i - 1] + 1 - nums[i]
            moves += increment
            nums[i] += increment
    return moves

# Example usage
print(minIncrementForUnique([3,2,1,2,1,7]))
← Back to All Questions