> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/array/remove-duplicates.md).

# Remove Duplicates

{% hint style="info" %}
Array, Two Pointers
{% endhint %}

Given an integer array `nums` sorted in non-decreasing order, remove the duplicates [in-place](https://en.wikipedia.org/wiki/In-place_algorithm) such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in `nums`.

Consider the number of unique elements of `nums` to be k, to get accepted, you need to do the following things:

Change the array `nums` such that the first k elements of `nums` contain the unique elements in the order they were present in `nums` initially. The remaining elements of `nums` are not important as well as the size of `nums`. Return `k`.

### Solutions

The key to solving this problem is understanding that you’re working with a sorted array, which means all duplicates of a particular number are adjacent to each other. This property allows you to effectively remove duplicates by comparing each element with its next one. The in-place requirement means you should not use additional space proportional to the size of the input array. You can use a constant amount of extra space, though. The relative order of the elements should be kept the same, meaning that you should not sort the array or change the order of unique elements. Finally, you should return the number of unique elements after removing duplicates. The remaining elements of the array after the first `k` are not important.

#### Approach - Brute Force Technique

This approach uses a temporary array to store the unique elements from the original array. It iterates through the original array and checks if the current element is different from the next one. If it is, the current element is stored in the temporary array. After the iteration, the last element of the original array is also stored in the temporary array. Finally, the unique elements from the temporary array are copied back to the original array. The function returns the number of unique elements.

**Steps**

1. **Empty Array Check:** If the length of `nums` is 0, the method returns 0. This is because there are no elements to process in an empty array.
2. **Temporary Array Initialization:** A temporary array `temp` of the same length as `nums` is created. This array is used to store the unique elements from `nums`.
3. **Variable Initialization:** A variable `j` is initialized to 0. This variable is used as an index for the `temp` array.
4. **Iteration Over `nums`:** The method iterates over the `nums` array from the first element to the second last element. For each element at index `i`, it checks if it is different from the next element at index `i + 1`.
5. **Storing Unique Elements:** If the current element is different from the next one, it means that the current element is unique and it is stored in the `temp` array at index `j`. Then, `j` is incremented by 1.
6. **Storing the Last Element:** After the iteration, the last element of `nums` is stored in `temp` at index `j`, and `j` is incremented by 1. This is done because the last element is not checked in the iteration.
7. **Copying Back to `nums`:** The unique elements from `temp` are copied back to `nums` from index 0 to `j - 1`.
8. **Return Value:** The method returns `j`, which is the number of unique elements in `nums`.

```csharp
public class Solution
{
    public int RemoveDuplicates(int[] nums)
    {
        if (nums.Length == 0) return 0;
        int[] temp = new int[nums.Length];
        int j = 0;
        for (int i = 0; i < nums.Length - 1; i++)
        {
            if (nums[i] != nums[i + 1])
            {
                temp[j++] = nums[i];
            }
        }
        temp[j++] = nums[nums.Length - 1];
        for (int i = 0; i < j; i++)
        {
            nums[i] = temp[i];
        }
        return j;
    }
}
```

> Complexity

* **Time complexity:** `O(N)`
* **Space complexity:** `O(N)`

**Approach - Two Pointers**

This approach avoids the use of extra space by maintaining a pointer that keeps track of the position of the last unique element in the original array. It iterates through the original array and checks if the current element is different from the element at the pointer’s position. If it is, the pointer is moved one step forward and the current element is stored at the pointer’s position in the original array. The function returns the number of unique elements.

#### Steps

1. **Check for Empty Array**: The function first checks if the input array `nums` is empty. If it is, it immediately returns 0, as there are no elements and hence no duplicates.
2. **Initialization**: A variable `i` is initialized to 0. This variable will serve as a pointer to the last non-duplicate element in the array.
3. **Iteration**: The function then enters a loop that starts from the second element of the array (index 1) and goes up to the last element. The loop variable `j` serves as a pointer to the current element being checked.
4. **Check for Duplicates**: Inside the loop, the function checks if the current element `nums[j]` is different from the last non-duplicate element `nums[i]`. If it is, it means `nums[j]` is not a duplicate of the last non-duplicate element.
5. **Update Non-Duplicate Element**: If `nums[j]` is not a duplicate, the function increments `i` and updates `nums[i]` to `nums[j]`. This effectively moves the non-duplicate element to the next position in the array, right after the last non-duplicate element.
6. **Return Result**: After the loop finishes, the function returns `i + 1`, which is the number of non-duplicate elements in the array.

```csharp
public class Solution
{
    public int RemoveDuplicates(int[] nums)
    {
        if (nums.Length == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.Length; j++)
        {
            if (nums[j] != nums[i])
            {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
}

```

> Complexity

* **Time complexity:** `O(N)`
* **Space complexity:** `O(1)`