Is it possible to find the first duplicate item in the array without using any data structure and the complexity should be less than or equals to O(n)

user_11142175 0
Viewed 197

If there is a random array say arr = [3, 5, 1, 4, 3] and N = 5 which indicates the size of the given array, is there a way to find the first repetitive value in the array (here the answer is 3) within O(N) time complexity but without using any data structure as a dictionary, map, tree, etc.. But you can use a variable.

The idea is to have an optimal space complexity.

I was asked this question in an interview.

Generally, this is solved by using a dictionary and keep the traversed item of the array as a key and value as a count. When we reach the count of more than 2 then we have a solution. But if we are not going to use the data structure, then we have to have loop within a loop to look up to the next items.

I also tried to think of a solution by using just one variable, but a variable will not be enough.

I think it is quite impossible to get the solution in O(N). However, I could be wrong. Please help me find a solution to this.

EDITED

My apologies for not mentioning this before. The numbers with in the array will able be from 1 <= N, i.e., 1 <= arr[i] <= N

duplicates time-complexity arrays algorithm
4 Answers

A simple solution would be to encode the information in the given array, if that is allowed:

for (int i = 0; i < arr.length; i++) {
    int number = arr[i] < 0 ? -arr[i] : arr[i];
    if (arr[number - 1] < 0)
        // to restore the original array do:
        // for (j = 0; j < arr.length; j++) if (arr[j] < 0) arr[j] *= -1;
        return number;
    else
        arr[number - 1] = -arr[number - 1];
}

Instead of returning the solution immediately you could modify the array again (see comment), so that it is the same as the input. If a temporary modification is not possible either, then you probably need to work with permutation cycles. See very similar question: Find a duplicate in array of integers

user_47851100

Please ask questions if you need more explanation of the logic. All the number are from 1 ... to N, as the PO just updates. It just use the same array/list to do the record-keeping. [Note] it's assuming there is only ONE duplicate number in the list.

A = [3,  1, 2, 5, 4, 3]   # 
#    *               *  

N  = len(A)

for i in range(N):
    x = A[i] % N

    A[x] +=  N

print('the duplicate number: ')

for i in range(N):
    if A[i] > N * 2:     #   
        print(i)         # 3
user_107607680

If you can alter the array, you can walk through the array repeatedly swapping the current element into its correct position until you find the duplicate.

for i = 0 to N-1
  while arr[i] != i && arr[i] != arr[arr[i]] do
    swap(arr[i], arr[arr[i]])
  end
  if arr[i] != i
    return arr[i]
  end
end

It's unclear to some people why this is O(N).

When the outer loop encounters an element which isn't at the matching index, it will swap it with the element at that index.

Each swap reduces the number of elements not at their matching index by either 1 or 2. Therefore, there can be at most N swaps since in the worst case, at most all N elements aren't at their matching index.

E.g., arr = [3, 5, 1, 4, 3] (1 indexed as in the OP's example).

swap 1: 3 with arr[3] yield [1, 5, 3, 4, 3] Here we got lucky and reduced the elements not in the matching position by 2.

swap 2: 5 with arr[5] yields [1, 3, 3, 4, 5]

swap 3: 3 with arr[3]: we terminate because we found a match.

user_20410770

Some people have mentioned using a bitarray to store the seen values. Note that this will only work if N is less than 32 (or however many bits your language can handle e.g. python can automatically handle > 32 bits).

Space Complexity: O(1)

def solution(a):

    bitarray = 0 << len(a)
    
    for num in a:
        bitmask = 1 << num;
        
        if ((bitarray & bitmask) == 0) :
            bitarray = bitarray + bitmask
        else:
            return num
    
    // not found
    return -1;
user_150885750
Related