Remove Duplicates from Sorted Array II
Given a sorted array, remove the duplicates from the array in-place such that each element appears at most twice, 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 6, with the first six elements of the array being [1, 1, 3, 5, 5, 7]Remove Duplicates from Sorted Array II solution in Java
This problem is an extension of the problem Remove duplicates from Sorted Array
It can also be solved in O(n) time complexity by using two pointers (indexes).
class RemoveDuplicatesSortedArrayII {
private static int removeDuplicates(int[] nums) {
int n = nums.length;
/*
* This index will move when we modify the array in-place to include an element
* so that it is not repeated more than twice.
*/
int j = 0;
for (int i = 0; i < n; i++) {
/*
* If the current element is equal to the element at index i+2, then skip the
* current element because it is repeated more than twice.
*/
if (i < n - 2 && nums[i] == nums[i + 2]) {
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 = 6
Array = 1 1 3 5 5 7