# Remove Duplicates from Sorted Array

Given a sorted array **`nums`**, 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 1:**

```
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 returned length.
```

**Example 2:**

```
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.
```

**Clarification:**

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by **reference**, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

```java
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
```

## Analysis

### **Two Pointers 快慢指针:**

两个指针，`i`，`j`：

`i` - 顺序存储下一个unique元素的index

`j` - 寻找下一个unique元素的index

主要逻辑是：

内层循环：只要`nums[j] == nums[j + 1]` 则 `j++`。若循环结束，说明`j+1`位置是下一个unique元素，而`j`位置是本次外层循环需要存的unique元素的index。`j`的额外说明：内层循环结束时，j是当前unique元素组的最后一个index。

外层循环：每次`nums[i] = nums[j]`，将`nums[j`]赋值给`nums[i]`，（`0 ~ i`代表排序好的unique元素）

两层循环结束时，`i`指向下一个待填入元素的index，因此实际`0 ~ i - 1`位置是我们所需元素，但是新数组总长度恰好也是 `i - 1 + 1` = `i`

```
Just illustrates index changes, keeping original nums[] array as reference

-------------

1st inner loop ends

[1, 1, 2, 2, 3]
 ^  ^
 i  j

i = 0, j = 1


1st outer loop ends:

[1, 1, 2, 2, 3]
    ^  ^
    i  j

i = 1, j = 2

-------------

2nd inner loop ends:

[1, 1, 2, 2, 3]
    ^     ^
    i     j

i = 1, j = 3

2nd outer loop ends:

[1, 1, 2, 2, 3]
       ^     ^
       i     j

i = 2, j = 4
```

**另一种Two Pointers实现，同样是slow, fast runner:**

<https://leetcode.com/articles/remove-duplicates-from-sorted-array/>

> Since the array is already sorted, we can keep two pointers i and j, where `i` is the slow-runner while `j` is the fast-runner. As long as `nums[i] = nums[j]`, we increment `j` to skip the duplicate.
>
> When we encounter `nums[j] !​=nums[i]`, the duplicate run has ended so we must copy its value to `nums[i + 1]`. ii is then incremented and we repeat the same process again until `j` reaches the end of array.

外层循环 j (1 \~ nums.length - 1)，只要`nums[j] != nums[i]`就更新i为`i++` ，并存入`nums[i] = nums[j]`

这种思路其实更简洁， input: `[1, 1, 2, 2, 3]`：

```
[1, 1, 2, 2, 3]
 ^  ^
 i  j


[1, 1, 2, 2, 3]
 ^     ^
 i     j

nums[j] != nums[i] 
nums[++i] = nums[j]


[1, 2, 2, 2, 3]
    ^  ^
    i  j


[1, 2, 2, 2, 3]
    ^     ^
    i     j


[1, 2, 2, 2, 3]
    ^        ^
    i        j

nums[j] != nums[i] 
nums[++i] = nums[j]


[1, 2, 3, 2, 3]
       ^     ^
       i     j

Loop ends, return i + 1
```

## Solution

Two Pointers - O(n) time, O(1) space - each i, j traverse at most n steps

```java
class Solution {
    public int removeDuplicates(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        // i - the index to store unique element
        // j - the index that search next unique element
        int i = 0, j = 0;
        while (i < n && j < n) {
            // searching for next unique element
            while(j < n - 1 && nums[j] == nums[j + 1]) {
                j++;
            }
            // the next unique element found is (starting) with index j+1
            // current index for unique to be stored is j
            // the index to store unique element is i 
            nums[i] = nums[j];
            i++;
            j++;
        }
        return i;
    }
}
```

Another Two Pointers

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