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;
}

Remove Duplicates from Sorted Array