Remove duplicates from sorted array, in place

Question

I solved this problem:

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

How can I improve its execution time? Is there any better way of doing it?

public int removeDuplicates(int[] numbers) {
    if(numbers.length == 0 || numbers.length == 1) {
        return numbers.length;
    }
    int indexForUniqueElements = 0;
    for (int index = 0; index < numbers.length - 1; index++) {
        if (numbers[index] != numbers[index+1]) {
            numbers[indexForUniqueElements++] = numbers[index];
          }
    }
    numbers[indexForUniqueElements++] = numbers[numbers.length - 1];
    return indexForUniqueElements;
  }

Answer 1

I don't see any way to greatly increase performance since your algorithm is already O(n).

However, there is a minor optimization that can be made. You should try to avoid having a calculation as the limit in a for loop. This gets calculated on each iteration of the loop. Initialize a variable with the result and use that instead:

public int removeDuplicates(int[] numbers) {
    if(numbers.length == 0 || numbers.length == 1) {
        return numbers.length;
    }
    int indexForUniqueElements = 0;
    int limit = numbers.length - 1;
    for (int index = 0; index < limit; index++) {
        if (numbers[index] != numbers[index+1]) {
            numbers[indexForUniqueElements++] = numbers[index];
          }
    }
    numbers[indexForUniqueElements++] = numbers[numbers.length - 1];
    return indexForUniqueElements;
  }

Answer 2

    if(numbers.length == 0 || numbers.length == 1) {

Could be

    if (numbers.length <= 1) {

Trivial time improvement (perhaps none; the compiler may optimize the original). Mostly preferable for simplicity's sake.

    int indexForUniqueElements = 0;
    for (int index = 0; index < numbers.length - 1; index++) {
        if (numbers[index] != numbers[index+1]) {
            numbers[indexForUniqueElements++] = numbers[index];
          }
    }

This is more problematic. What happens if the elements of the array are already unique? You'll copy the entire array for no reason. Consider breaking this up into two loops.

    int uniqueCount = 1;
    while (uniqueCount < numbers.length && numbers[uniqueCount - 1] != numbers[uniqueCount]) {
        uniqueCount++;
    }

    for (int index = uniqueCount + 1; index < numbers.length; index++) {
        if (numbers[index - 1] != numbers[index]) {
            numbers[uniqueCount] = numbers[index];
            uniqueCount++;
        }
    }

Now, we skim over all the unique numbers. Once we find the first duplicate, we stop. The earliest that duplicate can be is position 1. Because there are no numbers before that to duplicate. We don't have to copy any of these numbers, as they are already in the array.

The second loop copies subsequent unique numbers over top the duplicates and numbers out of order. If there are no duplicates (the first loop skimmed the entire array), then the second loop won't run at all.

I changed the name to uniqueCount because I found it more descriptive of what the variable holds. At any moment, it tells us how many known unique elements are in the array. By contrast, I don't really know what an indexForUniqueElements is. I figured it out, but with uniqueCount, I don't need to do so.

I moved the increment of uniqueCount in the second loop to its own line for readability.

This saves the extra assignment at the end of your loop. Your loop is trying to copy the number at the lower index of the comparison. My loop assumes that they are already in the right place. It copies the number at the higher index. Another trivial improvement (sometimes this will not do an assignment at the end when your original code would have).

This approach will not change the asymptotic performance. It's still \$\mathcal{O}(n)\$. But it may make the program run faster, as it saves copying values that are already in the right place. And copying is an expensive operation.

The only way to make a significant improvement from here would be to include the duplicate check with the sort. I.e. remove duplicates as you sort. But if you don't have control over the sort, there is no way that you can do that.

Answer 3

Your test numbers.length == 0 || numbers.length == 1 could be simplified as numbers.length < 2.

Multiple return statement should be avoided. You could set indexForUniqueElements to numbers.length when less than 2, and use just one return statement at the end.

You are reading each element from the numbers[index] array multiple times. Once in the duplicate test as the lhs, once in the duplicate test as the rhs, and possibly a third time to copy it into its new location. You could read the number once, into a local variable, and then reference the local variable. An enhanced for loop will do this for you, but you'd lose the index, which you use for testing against numbers[index+1]. You could instead test against the last value you read (cached in a local variable), and then you'd be free to use the enhanced for loop. The only difficultly is how to handle the first value, which has no previous. This can be trivially handled by using the first value in the array as the last value, and starting the fill-in index at 1.

Here is a simple implementation of the above. Each element of the numbers[] array is read from only once, apart from the first element (which is read twice):

public int removeDuplicates(int[] numbers) {
     int idx = 0;
     if (numbers.length > 0) {
         int last = numbers[idx++];
         for (int number : numbers)
             if (number != last)
                 last = numbers[idx++] = number;
     }
     return idx;
 }