# Question

Formatted question description: https://leetcode.ca/all/26.html

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array 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.

@tag-array


# Algorithm

Use fast and slow pointers to record the traversed coordinates. At the beginning, both pointers point to the first number. If the two pointers point to the same number, the fast pointer will move forward. If they are different, both pointers will move forward. One step, so that when the fast pointer goes through the entire array, the current coordinate of the slow pointer plus 1 is the number of different numbers in the array.

# Code

Java

• 
// same thing, two pointers
public class Remove_Duplicates_from_Sorted_Array {

public class Solution {
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}

int i = 0; // slow pointer
int j = 0; // fast pointer

while(j < nums.length) {
while(j + 1< nums.length && nums[j] == nums[j + 1]) {
j++;
}

nums[i] = nums[j];

i++;
j++;
}

return i; // i is incremented, but is index. So same as length
}
}

}

• // OJ: https://leetcode.com/problems/remove-duplicates-from-sorted-array/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int removeDuplicates(vector<int>& A) {
int j = 0;
for (int n : A) {
if (j - 1 < 0 || A[j - 1] != n) A[j++] = n;
}
return j;
}
};

• class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 1:
return len(nums)
slow = 0
for i in range(1, len(nums)):
if nums[i] != nums[slow]:
slow += 1
nums[slow] = nums[i]
return slow + 1