Complexity of removing duplicates by shifting elements

Question

Following code is trying to remove duplicates from a sorted array by overwriting repeated elements. Although it has nested for loops, its complexity is definitely less than O(n^2). What will be the complexity of following code?

    int n = arr.length;
    for(int i=0;i<n;i++){

        if(arr[i]==arr[i+1]){
            for(int j=i+1;j<n-1;j++){
                arr[j]=arr[j+1];
            }
            n--; i--; 
        }   
    }

In the worst-case, the array would be filled with pairs, and every step through `i` would cause the inner loop to execute. So, it's [still O(n^2)](http://stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop) — Blorgbeard, May 12 '16 at 22:05

Adnan Isajbegovic · Accepted Answer · 2016-05-13T05:08:12.643

Lets start from first position. Its for sure not duplicate, so you don't do any moving. Then we move to second position. It can be duplicate from first position value, and then, it may not be. If it is, then you have to move it to the end, so, for first 2 positions, you have two scenarios, one is just moving through array (its not duplicate), second one is moving element to the end of array, which require n-2 operations of arr[j]=arr[j+1].

Now, in case we moved third value to second position, we are still on it (i-- part). It can be duplicate of first value, and maybe it isn't. For first option you have to take n-3 (since you did n--, so you move it from position 2 to position n-1) operations of arr[j]=arr[j+1]. Now, if second value was not duplicate of first value (so you didn't do i-- and n--), but third value is duplicate of one of first two values, you still have to do n-3 operations of arr[j]=arr[j+1] (from position 3 to position n). So, number of operations stay the same in each case.

So, we have a pattern here: n-2 + n-3 + n -4 + ... + 3 + 2 + 1 of moving things around. This sum is:

n-2 + n-3 + n -4 + ... + 3 + 2 + 1 = n(n+1)/2 - n - n + 1

So based on this, since first part is moving through array, which is O(n), complexity of this algorithm is O(n^2). Worst case scenarios is having all same values in array.

Now, there is a better way. Place all values in Set. This require moving through array (O(n)), and checking if something is in Set, which is O(1). Then take all results from Set, and place them in array, which is O(n). So, complexity of such algorithm is O(n).

Complexity of removing duplicates by shifting elements

1 Answers1