Problem
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. Return the number of unique elements.The first k elements of nums should contain the unique elements in their original order. The remaining elements beyond the first k positions are not important.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,1,2]Output
2, nums = [1,2,_] Solution
This solution uses the Two Pointer technique. Since the array is already sorted, duplicate elements appear next to each other.One pointer tracks the position where the next unique element should be placed, while the other pointer scans the array. Whenever a new unique element is found, it is copied to the next available position.
After the traversal, the first k positions contain all unique elements, where k is the number of unique values.
public int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int k = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]) {
nums[k] = nums[i];
k++;
}
}
return k;
}
Complexity
The algorithm traverses the array only once, and each element is processed exactly once, resulting in a time complexity ofO(n).
The elements are modified directly within the original array, and only a few variables are used, so the extra space complexity is
O(1).