# 26\_Remove Duplicates from Sorted Array

## 28. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by **modifying the input array** [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) with O(1) extra memory.

**Example:**

```
Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the new length.
```

## Solution 1

If we really want to delete those duplicated elements:

```python
def removeDuplicates(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    i = 1
    while i < len(nums):
        if nums[i] == nums[i-1]:
            nums.pop(i)
        else:
            i += 1
    return len(nums)
```

## Solution 2

If we can just put those non-duplicated elements at the begining of the array:

Need two pointers. Use fast pointer to loop from left to right. Use slow pointer to record the first place that have duplicates.

Time complexity: $$O(n)$$

Space complexity: $$O(1)$$

```python
def removeDuplicates(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """ 

    # corner case
    if len(nums) == 0:
        return 0

    # write_index is the position for next write (slow pointer)
    # write_index-1 is the position for latest value
    write_index = 1

    # i is the faster pointer
    for i in range(1, len(nums)):
        if nums[write_index - 1] != nums[i] :
            nums[write_index] = nums[i]
            write_index += 1
    return write_index
```

### Variant

* Leetcode 27
* Leetcode 80