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

# 🚀 _4. Make array elements unique_ 🧠

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/sorting-bonus-problems/problem/make-array-elements-unique--170645)

## 💡 **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)

```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;
    }
};
```

<details>
  <summary><h2 align='center'>👨‍💻 Alternative Approaches</h2></summary>

### Alternative Approach (Using Greedy Optimization)

```cpp
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;
    }
};
```

</details>

## Code (Java)

```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)

```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](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

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

---

<div align="center">
  <h3><b>📍Visitor Count</b></h3>
</div>

<p align="center">
  <img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" />
</p>