# 26. Remove Duplicates from Sorted Array

Remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

```
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
```

Return the number of unique elements in `nums`.

***

### Intuition

* A number is unique if `nums[i] != nums[i-1]`
* If its not unique we can overwrite it with the next greater element.

### Approach

* Start from the beginning with `i=0` & `j=0`
  * `i` is fast points to current element & `j` is slow pointing to the previous element.
* Only if the previous pointed element is not equal to the current element we increase `j`.
  * write current value in its place

### Complexity

* **Time complexity** : $\text{O}(n)$
  * we iterate the array only once
* **Space complexity** : $\text{O}(1)$
  * we do operation in-place, no extra space needed

### Code

```java
public int removeDuplicates(int[] nums) {
	int j = 0;

	for (int i = 0; i < nums.length; ++i) {
		// If the element are not equal only then add to array
		if(nums[i] != nums[j]) {
			nums[++j] = nums[i];
		}
	}
	return j+1;
}
```

**Alternate Solution**

Count the number of places to shift each element

```java
public int removeDuplicates(int[] nums) { 
	int shiftPlacesBy = 0; 
	for (int i = 1; i < nums.length; ++i) { 
		// if elements are equal we increase the shift count by
		if(nums[i] == nums[i-1]) { 
			shiftPlacesBy++; 
			continue; 
		} 
		nums[i - shiftPlacesBy] = nums[i]; 
	} 
	return nums.length - shiftPlacesBy; 
} 
```

| Space Complexity | Time Complexity |
| ---------------- | --------------- |
| $$\text{O}(1)$$  | $$\text{O}(n)$$ |

* we iterate the array only once
* we do operation in-place, no extra space needed