Insert a smallest possible positive integer into an array of unique integers [duplicate]

Question

I am trying to tackle this interview question: given an array of unique positive integers, find the smallest possible number to insert into it so that every integer is still unique. The algorithm should be in O(n) and the additional space complexity should be constant. Assigning values in the array to other integers is allowed.

For example, for an array [5, 3, 2, 7], output should be 1. However for [5, 3, 2, 7, 1], the answer should then be 4.

My first idea is to sort the array, then go through the array again to find where the continuous sequence breaks, but sorting needs more than O(n).

Any ideas would be appreciated!

Answer 1

My attempt:

The array A is assumed 1-indexed. We call an active value one that is nonzero and does not exceed n.

• Scan the array until you find an active value, let A[i] = k (if you can't find one, stop);

• While A[k] is active,

  • Move A[k] to k while clearing A[k];

• Continue from i until you reach the end of the array.

After this pass, all array entries corresponding to some integer in the array are cleared.

• Find the first nonzero entry, and report its index.

E.g.

[5, 3, 2, 7], clear A[3]
[5, 3, 0, 7], clear A[2]
[5, 0, 0, 7], done

The answer is 1.

E.g.

[5, 3, 2, 7, 1], clear A[5],
[5, 3, 2, 7, 0], clear A[1]
[0, 3, 2, 7, 0], clear A[3],
[0, 3, 0, 7, 0], clear A[2],
[0, 0, 0, 7, 0], done

The answer is 4.

The behavior of the first pass is linear because every number is looked at once (and immediately cleared), and i increases regularly.

The second pass is a linear search.

---

A= [5, 3, 2, 7, 1]
N= len(A)

print(A)
for i in range(N):
    k= A[i]
    while k > 0 and k <= N:
        A[k-1], k = 0, A[k-1] # -1 for 0-based indexing
        print(A)

[5, 3, 2, 7, 1]
[5, 3, 2, 7, 0]
[0, 3, 2, 7, 0]
[0, 3, 2, 7, 0]
[0, 3, 0, 7, 0]
[0, 0, 0, 7, 0]
[0, 0, 0, 7, 0]

---

Update:

Based on גלעד ברקן's idea, we can mark the array elements in a way that does not destroy the values. Then you report the index of the first unmarked.

print(A)
for a in A:
    a= abs(a)
    if a <= N:
        A[a-1]= - A[a-1] # -1 for 0-based indexing
    print(A)

[5, 3, 2, 7, 1]
[5, 3, 2, 7, -1]
[5, 3, -2, 7, -1]
[5, -3, -2, 7, -1]
[5, -3, -2, 7, -1]
[-5, -3, -2, 7, -1]

Answer 2

From the question description: "Assigning values in the array to other integers is allowed." This is O(n) space, not constant.

Loop over the array and multiply A[ |A[i]| - 1 ] by -1 for |A[i]| < array length. Loop a second time and output (the index + 1) for the first cell not negative or (array length + 1) if they are all marked. This takes advantage of the fact that there could not be more than (array length) unique integers in the array.