Move duplicates to the end of a sorted array

If your values are in limited range, there exists solution in O(n) time and O(1) space.

Determine the maximum value in array. Get some constant C > arraymax, as example - C = 10 for your array.

Scan array, squeezing unique values and counting duplicates for every value. If value V has K>0 duplicates, write V+C*K instead of value.

At the next scan find values with duplicates, extract number of duplicates and write them after squeezed unique values.

def dedup(lst):
    mx = max(lst) + 1
    dupcnt = 0
    delcnt = 0
    start = 0
    for i in range(1, len(lst) + 1):
        if i == len(lst) or (lst[i] != lst[start]):
            lst[start - delcnt] = lst[start] + dupcnt * mx
            delcnt += dupcnt
            start = i
            dupcnt = 0
        else:
            dupcnt += 1
    dupidx = len(lst) - delcnt
    for i in range(0, len(lst) - delcnt):
        dupcnt = lst[i] // mx
        if dupcnt:
           lst[i] %= mx
           for j in range(dupidx, dupidx+dupcnt):
              lst[j] = lst[i]
           dupidx += dupcnt
    return lst

print(dedup([1,2,2,2,3,4,4,5]))
>>> [1, 2, 3, 4, 5, 2, 2, 4]

You need to have 2-3 pointers (indexes). i: the next unique elements will be put at this position j: linear traversal pointer on the list

private static void fix(int[] nums) {
    int i = 0;
    int j = 0;
    while (j < nums.length) {
        int k;
        for (k = j + 1; k < nums.length && nums[k] == nums[j]; k++) {

        }

        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
        j = k;
        i++;
    }
}

At the risk of stating the obvious . . . an approach in O(n log n) time and O(1) extra space is:

1. Scan through the array to find the first element with each value, and swap that element directly into the correct position. (For example, when you reach the fourth distinct value, you swap the first element with that value into position #4.)
   • This step requires O(n) time and O(1) extra space.
   • After this step, the array consists of all unique elements in the correct order, followed by all the duplicates in garbage order.
2. Sort the duplicates using heapsort.
   • This step requires O(n log n) time and O(1) extra space.

UPDATE: Misread your intentions where your concern was on space, this is the PHP version of "pointers". Since it's sorted we can just go through the loop once, right ? If not we would probably bake in duplicate sorting into the sort itself.

function findRepeating(&$arr)
{
    $size = count($arr);
    $previous = -99999;
    for ($i = 0; $i < $size; $i++) {
        if ($i>0)
            $previous = $arr[$i-1];

        if ($arr[$i] == $previous) {
            array_push($arr,$arr[$i]); //push to end
            unset($arr[$i]); //then remove current one
        }
    }
    var_dump($arr);
}

We basically just take the current size of array and when we find duplicates push to the end of the array expanding it's size a little which is offset by the unset().

array(7) {
  [0]=>
  string(1) "1"
  [2]=>
  string(1) "2"
  [3]=>
  string(1) "3"
  [4]=>
  string(1) "4"
  [6]=>
  string(1) "5"
  [7]=>
  string(1) "1"
  [8]=>
  string(1) "4"
}

In a lower level language you could just shuffle around pointers because you know the end value so you take note of that and just append duplicates after that and add to the offset as it goes along. Totally achievable with or without arrays, with arrays we just swap around. My example is in PHP so instead of shuffling I just expand the array so I just use a single extra space temporarily .

Not entirely clear one how multiple duplicates should be handled, or what you're asking precisely, but I assume it's that you want to make sure that O(1) space is satisfied, regardless of time complexity, so that's what I'll attempt to answer.

With arrays, O(1) space, O(N^2) time:

You can do it in place by simply swapping the duplicate elements to the end. You can find duplicate elements by keeping a "current" pointer and simply checking that the "next" element isn't the same as the "current". This is O(n^2) time in the worst case. Example:

[1,1,2,3,4,4,5] # "cur" is index 0 (element 1), and "next" is index 1 (element 1). Swap "next" to end.
[1,2,1,3,4,4,5] # swapping
[1,2,3,1,4,4,5] # swapping
...             # Tedious swapping
[1,2,3,4,4,5,1] # Done swapping. Increment "cur".
[1,2,3,4,4,5,1] # "cur" is index 1 (element 2), and "next" is index 2 (element 3). Increment "cur"
...             # Boring (no duplicates detected)
[1,2,3,4,4,5,1] # "cur" is index 3 (element 4), and "next" is index 4 (element 4). Swap "next" to end.
[1,2,3,4,5,4,1] # swapping
[1,2,3,4,5,1,4] # Done swapping. Increment "cur"
...             # No more duplicates
# Done

As an aside, in practice trading time for less space typically isn't worth it. Memory is cheap, but slow response times can lose users, which is expensive. A notable exception is embedded systems where memory might be tight and inputs are short (on small inputs asymptotic runtime isn't relevant).

With linked lists, O(1) space, O(N) time:

If you had a linked list instead of an array, you could do this in O(n) time and O(1) space quite easily. Linked lists have the advantage over arrays when you're forced to "shift" elements around since they can move pointers instead of moving ALL elements by a position. The cur/next strategy is similar for linked lists as above with the array. Here's an example:

1->1->2->3->4->4->5 # "cur" is first element (value 1), and "next" is second element (value 1). Swap "next" to the end.

1
 \
1->2->3->4->4->5    # Move "cur"'s pointer to "next"'s next element.

1->2->3->4->4->5->1 # Set "next"'s pointer to null, set tails pointer to "next"

...                 # Boring stuff with no duplicates

1->2->3->4->4->5->1 # "cur" is fourth element (value 4), and "next" is fifth element (value 4). Swap fifth element to end.

         4
          \
1->2->3->4->5->1    # Move "cur"'s pointer to "next"'s next element.

1->2->3->4->5->1->4 # Set "next"'s pointer to null, set tails pointer to "next"

...                 # No more duplicates
# Done (hopefully it's clear moving and element to the end is O(1) instead of O(n))

If you could beat an array into a linked list in O(n) time and O(1) space, the problem is solved. However, this isn't possible. Linked lists take up more space per element than an array does, so just by having a linked list anywhere in the program, I think O(1) space would be violated.

Since it was an interview question though, it might have been worth pointing out that linked lists are a bit better for solving this problem efficiently, regardless of the problem statement. Typically interviewers like to see that you can apply data structures properly, and sometimes they're amenable to an input type change.

Smart data structures and dumb code works a lot better than the other way around. --Eric S Raymond

Here's C code that puts the duplicated strings at the last of the array. The indicator array is used to indicates the index at which the string is duplicated. ie: if s[0]==s[1] then indicator[1] will be assigned to 0 as at this index the string is repeated. Then use indicator array to swap the duplicated string to last valid place in the array.

ie: if we found that indicator[1]=0 , this means that there is a duplicated string at index 1 and we need to move it to the last of the array, but what if the last element of the array is duplicated also!! then we should move forward to the second element from the end of the array

    void put_dublicates_to_last(char**s, int n)
{
    int i = 0, j = 0, flag = 0,counter=0;
    int* indicator = malloc(n * sizeof(int));
    char * temp;
    for (i = 0; i < n; i++)
        indicator[i] = -1;
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (strcmp(s[i], s[j]) == 0)
            {
                //swap with the last element
                counter++;
                indicator[j] = 0;
            }
        }
    }
    printf("counter is %d\n", counter);
    //use the indicator to swap with the last elements 
    for (i = 0; i < n; i++)
    {
        for (j = n; j >= 0; j--)
        {
            if (indicator[i] == 0)
            {
                if (indicator[j] != 0)
                {
                    //swap
                    temp = s[i];
                    s[i] = s[j-1];
                    s[j-1] = temp;
                    flag = 1;
                }
            }
            if (flag)
            {
                flag = 0;
                break;
            }

        }

    }

    for (i = 0; i < n; i++)
        printf("%s\n", s[i]);
}

This can be done with single pointer and another pointer to find the next maximum if we don't care about the stability and the sortedness of the duplicate elements in the array.

Algorithm

• Start a pointer and iterate through the array as long as the element that you are at is greater than the previous and lesser than the next
• Once you see a break in this pattern, stop the increment and find a number that is greater than the current
• Swap this number with the next greater number.
• Continue this search till you can't find any more numbers that are greater in the array
• Break out of the loop if this condition is reached and return back the array

public static void main(String[] args) {
        // TODO Auto-generated method stub              
        int[] arr = {11, 12, 12, 13, 14, 14, 14, 14,  15};
        rearrangeSort(arr);     
        for(int a : arr) {
            System.out.print(a + " ");
        }       
    }   
    public static void rearrangeSort(int[] arr){
        int unique = 1;
        int find = 0;
        while(unique < arr.length) {
            if(unique == 1 && (arr[unique - 1] == arr[unique])){
                find = findMax(arr, arr[unique], unique);
                swap(arr, unique, find);                
            }else if(unique == 1 && (arr[unique] == arr[unique + 1])){
                find = findMax(arr, arr[unique], unique);
                swap(arr, unique + 1, find);                
            }           
            if(unique > 0 && (arr[unique - 1] < arr[unique]) && (arr[unique] < arr[unique + 1])){
                unique++;
            }
            find = findMax(arr, arr[unique], unique);           
            if(find == 0) {break;}
            swap(arr, unique+1, find);
        }                   
    }       
    public static int findMax(int[] arr, int target, int index){
        while(index < arr.length) {
            if(arr[index] > target) {return index;}
            index++;
        }
        return 0;
    }       
    public static void swap(int[] arr, int idx1, int idx2){
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;       
    }
}