Remove Duplicates from Sorted Array
Given a sorted array, remove all the duplicates from the array 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.
Example
Given array [1, 1, 1, 3, 5, 5, 7]
The output should be 4, with the first four elements of the array being [1, 3, 5, 7]Remove Duplicates from Sorted Array solution in Java
Given that the array is sorted, all the duplicate elements will appear together.
We can solve the problem in O(n) time complexity by using two pointer pattern. We’ll keep two pointers (indexes) -
- One pointer
i, to iterate over the array, and - Another pointer
j, to keep track of the number of unique elements found so far. This index will move only when we modify the array in-place to include a new non-duplicate element.
class RemoveDuplicatesSortedArray {
private static int removeDuplicates(int[] nums) {
int n = nums.length;
/*
* This index will move only when we modify the array in-place to include a new
* non-duplicate element.
*/
int j = 0;
for (int i = 0; i < n; i++) {
/*
* If the current element is equal to the next element, then skip the current
* element because it's a duplicate.
*/
if (i < n - 1 && nums[i] == nums[i + 1]) {
continue;
}
nums[j++] = nums[i];
}
return j;
}
public static void main(String[] args) {
int[] nums = new int[] { 1, 1, 1, 3, 5, 5, 7 };
int newLength = removeDuplicates(nums);
System.out.println("Length of array after removing duplicates = " + newLength);
System.out.print("Array = ");
for (int i = 0; i < newLength; i++) {
System.out.print(nums[i] + " ");
}
System.out.println();
}
}# Output
Length of array after removing duplicates = 4
Array = 1 3 5 7