700246. Remove Duplicates Sorted Array
Here is a detailed blog post for the "Remove Duplicates Sorted Array" problem:
Remove Duplicates Sorted Array
Summary
This problem involves removing duplicate elements from a sorted array. The input array contains unique elements, but they may not be distinct. The goal is to create a new array with only one occurrence of each element in the original array, preserving the original order and maintaining the array's sorted property.
Detailed Explanation
The algorithmic approach for this problem involves using two pointers: i and j. Initialize both pointers at the beginning of the array (i = 0, j = 0). Iterate through the array with the following steps:
- Compare elements at indices
iandj(ifjis still within the array boundaries). - If they are equal, increment
jto move to the next element. - If they are not equal, copy the element at index
jto the position just after the last non-duplicate element (i++,j++). - Repeat steps 1-3 until
jreaches the end of the array.
The time complexity for this algorithm is O(n), where n is the length of the input array, since we make a single pass through the array. The space complexity is also O(n) because we create a new array with potentially fewer elements than the original array.
Here's an ASCII art diagram to illustrate the process:
Input Array: [1, 2, 2, 3, 4, 4, 5]
i = 0, j = 0
[1]
i = 1, j = 1
[1, 2]
j++
i = 2, j = 2
[1, 2, 3]
j++
i = 3, j = 3
[1, 2, 3, 4]
j++
i = 4, j = 4
[1, 2, 3, 4, 5]
Output Array: [1, 2, 3, 4, 5]
Optimized Solutions
Java
public int[] removeDuplicates(int[] arr) {
if (arr.length == 0) return arr;
int i = 0;
for (int j = 1; j < arr.length; j++) {
if (arr[j] != arr[i]) {
i++;
arr[i] = arr[j];
}
}
return Arrays.copyOfRange(arr, 0, i + 1);
}