# LeetCode • 26. Remove Duplicates from Sorted Array

## Problem

- Given a sorted array \(nums\), remove the duplicates in-place such that each element appears only once and returns the new length.
- Do not allocate extra space for another array, you must do this by modifying the input array in-place with \(O(1)\) extra memory.
- See problem on LeetCode.

## Algorithm

- 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] \neq nums[i]\), the duplicate run has ended so we must copy its value to \(nums[i + 1]\). \(i\) is then incremented and we repeat the same process again until \(j\) reaches the end of array.

## Code

```
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
"""
@param a list of integers
@return an integer
"""
# Handle the special case that A is empty
if not nums: # or "if not len(nums)" or "if len(A) == 0"
return 0
i = 0
for j in range(1, len(nums)):
# Not a duplicate item
if nums[i] != nums[j]:
i += 1
nums[i] = nums[j]
return i + 1
```

## Complexity analysis

- Time complexity: \(O(n)\). Assume that \(n\) is the length of array. Each of \(i\) and \(j\) traverses at most \(n\) steps.
- Space complexity: \(O(1)\).