# How to Remove Duplicates from a Sorted Array

Removing duplicates from a sorted array is a common problem asked in many coding interviews and programming challenges. This can be approached using different methods. In this article, we'll discuss two approaches to remove duplicates from a sorted array: one using **set** and another using the **two-pointers technique**.

### Solution 1: Brute Force Approach (using Set)

This method uses a **set** to store **unique elements**, ensuring that duplicates are removed.

**Implementation**:

```cpp
// Solution-1: Brute Force Approach (using Set)
// Time Complexity: O(nlogn)
// Space Complexity: O(n)
int removeDuplicates(vector<int> &arr, int n)
{
    set<int> uniqueElements;

    for (int i = 0; i < n; i++)
    {
        uniqueElements.insert(arr[i]);
    }

    int k = uniqueElements.size();

    // Copy unique elements from the set back into the input array
    int i = 0;
    for (auto x : uniqueElements)
    {
        arr[i] = x;
        i++;
    }

    // Return the number of unique elements
    return k;

}
```

**Logic**:

1. **Use a Set**: Insert all elements of the array into a set to remove duplicates.
    
2. **Get Unique Count**: The size of the set gives the number of unique elements.
    
3. **Copy Back to Array**: Copy elements from the set back to the array.
    

**Time Complexity**: O(n log n)

* **Explanation**: Inserting each element into the set takes O(log n) time, resulting in O(n log n) for n elements.
    

**Space Complexity**: O(n)

* **Explanation**: The set stores all unique elements, potentially up to n elements.
    

**Example**:

* **Input**: `arr = [1, 1, 2, 2, 3, 4, 4]`, `n = 7`
    
* **Output**: `k = 4`, `arr = [1, 2, 3, 4, ...]`
    
* **Explanation**: The array contains 4 unique elements.
    

---

### Solution 2: Optimal Approach (Two-Pointers Technique)

This method uses **two pointers** to overwrite duplicates **in place**, providing an efficient solution.

**Implementation**:

```cpp
// Solution-2: Optimal Approach (Two-Pointers Technique)
// Time Complexity: O(n)
// Space Complexity: O(1)
int removeDuplicates(vector<int> &arr, int n)
{
    int i = 0; // Pointer to track the position of the next unique element
    for (int j = 1; j < n; j++)
    {
        if (arr[i] != arr[j])
        {
            i++;
            arr[i] = arr[j];
        }
    }

    // Return the number of unique elements
    return i + 1;
}
```

**Logic**:

1. **Initialize Pointers**: Use `i` to track the position of the next unique element and `j` to traverse the array.
    
2. **Compare Elements**: If `arr[i]` is not equal to `arr[j]`, increment `i` and update `arr[i]` with `arr[j]`.
    
3. **Return Count**: The value `i + 1` gives the number of unique elements.
    

**Time Complexity**: O(n)

* **Explanation**: The array is traversed once.
    

**Space Complexity**: O(1)

* **Explanation**: No additional space is used apart from variables.
    

**Example**:

* **Input**: `arr = [1, 1, 2, 2, 3, 4, 4]`, `n = 7`
    
* **Output**: `k = 4`, `arr = [1, 2, 3, 4, ...]`
    
* **Explanation**: The array contains 4 unique elements.
    

---

### Comparison

* **Brute Force Method**:
    
    * **Pros**: Simple and straightforward.
        
    * **Cons**: Inefficient for large arrays due to O(n log n) time complexity and additional space usage.
        
    * **Use Case**: Useful when simplicity is more important than efficiency.
        
* **Optimal Method**:
    
    * **Pros**: Efficient with O(n) time complexity and O(1) space complexity.
        
    * **Cons**: Requires in-place modification of the array.
        
    * **Use Case**: Ideal for large arrays and when in-place operations are feasible.
        

### Edge Cases

* **Empty Array**: Returns 0 as there are no elements.
    
* **Single Element Array**: Returns 1 as a single element is trivially unique.
    
* **All Identical Elements**: Returns 1 as all elements are the same.
    

### Additional Notes

* **Efficiency**: The optimal approach is significantly more efficient for large datasets.
    
* **Simplicity**: Despite its efficiency, the optimal approach is simple to implement.
    
* **Practicality**: The optimal method is generally preferred due to its linear time complexity and constant space complexity.
    

### Conclusion

Removing duplicates from a sorted array can be done efficiently using an in-place approach with two pointers. While the brute force method provides a straightforward solution, the optimal approach is both efficient and easy to implement, making it suitable for large datasets.

---