Deepak Tiwari Deepak Tiwari - 1 year ago 74
Java Question

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

I had an interview and there was a question. Find unique numbers from sorted array in less than O(n) time.

Ex: 1 1 1 5 5 5 9 10 10
o/p 1 5 9 10

I gave the solution but that was of O(n). Can anyone help me with this thread.

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

Answer Source

Divide and conquer:

  • look at the first and last element of a sorted sequence (the initial sequence is data[0][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) {
    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]);