Remove Duplicates from Sorted Array
Given a sorted array, remove the duplicates in-place such that each element appears 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 with O(1) extra memory.
Constraints:
- 0 <= nums.length <= 3 * 10^4
- -10^4 <= nums[i] <= 10^4
- nums is sorted in ascending order
Examples:
Input: [1,1,2]
Output: 2
Explanation: 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.
Input: [0,0,1,1,1,2,2,3,3,4]
Output: 5
Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
Solutions
Two Pointers
We use two pointers, i and j, where i is the slow runner and j is the fast runner. If the elements at the i and j indices are different, we increment i and copy the element at the j index to the i index. This way, all the unique elements are moved to the front of the array.
var removeDuplicates = function (nums) {
let i = 0;
for (let j = 1; j < nums.length; j++) {
if (nums[j] !== nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
};
Follow-up:
How would you solve this problem if the array is not sorted?
