Single pass solution to 12.12: find missing and duplicate elements

#1

We can use the fact that elements are from 0 to n-1 and put each element in its “correct” (i == a[i]) position.
Since one element is missing, one position will not have correct element in it. Instead it will have duplicate element.

For example, for given array [5,3,0,3,1,2] we get [0,1,2,3,3,5]. Now it’s obvious that number 4 is missing and 3 occupies its space.

We have to be careful not to end up in infinite loop. We stop swapping when the element we swap with is the same as the current element.

int i = 0;
int lastMismatch = 0;
while (i < a.length) {
    while (i != a[i] && a[a[i]] != a[i]) {
        swap(a, i, a[i]);
    }

    if (i != a[i]) {
        lastMismatch = i;
    }

    i++;
}

System.out.println(lastMismatch + " is missing and " + 
                            a[lastMismatch] + " is duplicate");

The algorithm is O(1) space and O(n) running time, since each swap puts one element in its correct position.

0 Likes
#2

I think it is a good approach if you don’t consider the space you used in original space. However, technically you are just using the original input array as a hash table so I probably won’t call this an O(n) time and O(1) space solution; instead, it costs O(n) space :stuck_out_tongue:

0 Likes