Finding unique numbers from sorted array in less than O(n)

Question

I had an interview and there was the following question:

Find unique numbers from sorted array in less than O(n) time.

Ex: 1 1 1 5 5 5 9 10 10
Output: 1 5 9 10

I gave the solution but that was of O(n).

Edit: Sorted array size is approx 20 billion and unique numbers are approx 1000.

Answer 1

Divide and conquer:

• look at the first and last element of a sorted sequence (the initial sequence is data[0]..data[data.length-1]).
• If both are equal, the only element in the sequence is the first (no matter how long the sequence is).
• If the are different, divide the sequence and repeat for each subsequence.

Solves in O(log(n)) in the average case, and O(n) only in the worst case (when each element is different).

Java code:

public static List<Integer> findUniqueNumbers(int[] data) {
    List<Integer> result = new LinkedList<Integer>();
    findUniqueNumbers(data, 0, data.length - 1, result, false);
    return result;
}

private static void findUniqueNumbers(int[] data, int i1, int i2, List<Integer> result, boolean skipFirst) {

    int a = data[i1];
    int b = data[i2];

    // homogenous sequence a...a
    if (a == b) {
        if (!skipFirst) {
            result.add(a);
        }
    }
    else {
        //divide & conquer
        int i3 = (i1 + i2) / 2;
        findUniqueNumbers(data, i1, i3, result, skipFirst);
        findUniqueNumbers(data, i3 + 1, i2, result, data[i3] == data[i3 + 1]);
    }
}