26. Remove Duplicates from Sorted Array¶
Intitution¶
In a sorted array, duplicates are always next to each other. So use a slow and fast pointer where the slow only moves when an unique element is encountered. Just scan through the array, and whenever we see a new (unique) element, overwrite the front part of the array with it, maintaining only the distinct values in-place.
Complexity¶
| Space Complexity | Time Complexity |
|---|---|
| $\(\text{O}(1)\)$ | $\(\text{O}(n)\)$ |
Code¶
public int removeDuplicates(int[] nums) {
int i = 0, j = 0;
// Traverse the array
for(; i < nums.length;) {
// If first element or current is not equal to the previous (i.e., it's unique)
if(i == 0 || nums[i-1] != nums[i]) {
nums[j] = nums[i]; // Place the unique element at the next available position
j++; // Move the insert pointer
}
i++; // Move to the next element
}
return j; // j is the new length of the array with unique elements
}