LeetCode 25 – Remove Duplicates from Sorted Array

Posted on January 7, 2014

Last updated on January 7, 2014

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
Markdown SHA1: ae427e94cf6b0340b8867eb20ab1c94d2e4271d7