Solution to LeetCode Remove Duplicates from Sorted Array problem.
The idea is to partition the array into three distinct regions. The processed elements, the hole, and the unprocessed elements. More explanation in the Java code that follows:
/*
Idea: Partition the array into inclusive regions as follows:
[0..holeStart-1], [holeStart, holeStart+holeSize-1], [holeStart+holeSize, N-1]
Everything in [0..holeStart-1] appears only once and is sorted
[holeStart, holeStart + holeSize-1] is slice with elements that are all
duplicates and we can use that space for filling up with
other elements
[holeStart+holeSize, N-1] is the yet to be processed region
First, we find the start of a non-empty hole.
Then, we can fill up the hole with non-repeating elements
*/
public int removeDuplicates(int[] A) {
if(A.length <= 1) return A.length;
int holeSize = 0;
int holeStart = -1;
int idx = 0;
while(idx < A.length){
// Calculate how many times the current element is repeated
int occs = 1;
int idx1 = idx;
while(idx1+1 < A.length && A[idx1] == A[idx1+1]){
occs++;
idx1++;
}
// idx1 is last occurence of A[idx].
// Set the start of the hole if not initialized
if(occs > 1 && holeStart == -1){
holeStart = idx+1;
holeSize = idx1-idx;
idx = idx1;
}
else if(holeStart != -1){
A[holeStart] = A[idx];
holeStart++;
holeSize += (occs-1);
idx = idx1;
}
idx++;
}
return A.length - holeSize;
}