4. Make array elements unique.md

Difficulty	Source	Tags
Medium	160 Days of Problem Solving (BONUS PROBLEMS 🎁)	Arrays Hash Sorting

🚀 4. Make array elements unique 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Given an integer array arr[], your task is to find the minimum number of increment operations required to make all the array elements unique, i.e., no value in the array should occur more than once. In one operation, a value can be incremented by 1 only.

Note: The answer will always fit into a 32-bit integer.

🔍 Example Walkthrough:

Input:

arr[] = [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 fewer operations.

Input:

arr[] = [1, 2, 2]

Output:

1

Explanation:
After one operation [2 -> 3], the array could be [1, 2, 3].

Input:

arr[] = [5, 4, 3, 2, 1]

Output:

0

Explanation:
All elements are already unique.

Constraints:

• $1 ≤ arr.size() ≤ 10^6$
• $0 ≤ arr[i] ≤ 10^6$

🎯 My Approach:

Step-by-Step:

1. Sort the Array:
   Sorting the array ensures that duplicates are adjacent, simplifying the process of identifying and resolving conflicts.

2. Iterate and Adjust:

   • Traverse the sorted array.
   • For each element, check if it is less than or equal to the previous element. If true:
     • Increment the element to make it greater than the previous element.
     • Accumulate the number of increments required in a counter (ans).

3. Return the Result:

   • After processing all elements, the value of ans gives the minimum number of operations needed to make all elements unique.

🕒 Time and Auxiliary Space Complexity

• Expected Time Complexity:

  • Sorting: O(n log n)
  • Single traversal: O(n)
    Overall: O(n log n)

• Expected Auxiliary Space Complexity: O(1), as we only use constant extra space.

📝 Solution Code

Code (Cpp)

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

👨‍💻 Alternative Approaches

Alternative Approach (Using Greedy Optimization)

class Solution {
  public:
    int minIncrements(vector<int>& arr) {
        sort(arr.begin(), arr.end()); 
        int ans = 0, prev = arr[0];
        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] <= prev) {
                ans += (prev - arr[i] + 1);
                prev++;
            } else {
                prev = arr[i];
            }
        }
        return ans;
    }
};

Code (Java)

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

Code (Python)

class Solution:
    def minIncrements(self, arr): 
        arr.sort() 
        ans = 0
        for i in range(1, len(arr)):
            if arr[i] <= arr[i - 1]:
                ans += arr[i - 1] + 1 - arr[i]
                arr[i] = arr[i - 1] + 1 
        return ans

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count