Minimum Increment to Make Array Unique Leetcode Solution

Difficulty Level Medium
Frequently asked in Coursera Databricks eBay Square Twitter Uber
Array Greedy SortingViews 4820

Problem Statement:

Minimum Increment to Make Array Unique Leetcode Solution – 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.

Example:

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 with 5 or fewer moves that it is impossible for the array to have all unique values.

 

imageaMinimum Increment to Make Array Unique Leetcode Solution

Approach:

Idea:

  1. First, we need to sort the given array.
  2. When we find the condition that the current element is less than or equal to the previous elements then we need to update the current array element A[i] by A[i-1]+1.
  3. Also, in every iteration we need to keep track of results by result += A[i-1]+ 1 – A[i].
  4. Finally, we need to return the value stored in the result variable.

Code:

C++ Program of Minimum Increment to Make Array Unique:

class Solution {
public:
    int minIncrementForUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        long long c=0;
        for(int i=1;i<nums.size();i++){
            if(nums[i]<=nums[i-1]){
                c+=nums[i-1]+1-nums[i];
                nums[i]=nums[i-1]+1;
            }
        }
        return c;
    }
};

Java Program of  Minimum Increment to Make Array Unique:

class Solution {
    public int minIncrementForUnique(int[] nums) {
        Arrays.sort(nums);
        int c=0;
        for(int i=1;i<nums.length;i++){
            if(nums[i]<=nums[i-1]){
                c+=nums[i-1]+1-nums[i];
                nums[i]=nums[i-1]+1;
            }
        }
        return c;
    }
}

Complexity Analysis for Minimum Increment to Make Array Unique Leetcode Solution:

Time Complexity:

The Time Complexity of the code is O(NlogN ) + O(N) as we need to sort the array first and then traverse through the given array only once.

Space Complexity:

The Space Complexity of the code is O(1) because we don’t need any extra space to solve this problem.

Translate »