Move duplicates to the end of a sorted array

Question

I was asked this question in an interview. There is a sorted array with duplicates. The goal is to return the array with unique elements first and duplicates at the end preserving the order. For example [1, 1, 2, 3, 4, 4, 5] should become [1, 2, 3, 4, 5, 1, 4].

I was able to solve the question with an extra space (O(n) space) and linear time (O(n) time), but I am not sure if that is the best answer, ideally using no linear space.

I searched stackoverflow and found similar questions but not exactly the same. For example there was a question sorting an array and moving duplicates to the end, but in my case the array is already sorted and the goal is to only move duplicates to the end.

Answer 1

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

Answer 2

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]