Finding the missing value in the given range in constant space and O(n) time complexity

So, I came across this question recently which got me thinking for a while.

It’s easy to track frequency in a hash-table and spit out the number whose frequency is zero in O(n). But, we can’t use additional space.

But, as its mentioned in the question, the array’s length is equal to the range of the number.

This can help us use the input array as the hash-table.

Here, for each number in the array, we’ll use it as the key and put value equal to the number itself.

So, to represent if we have numbers 1 to 4 in an array of size 4, this is how our hash-map should look like:

[1,2,3,4]

So, lets take another example: [4,2,1,0]

If we can store the value of each element corresponding to it’s index, we should get a hash-map like this:

[1,2,0,4]

Note, we store the value at index -1 .

Since our index starts from zero and the range of the value is from 1 to N.

def missing_int(A):
    l=len(A)
    i=0
    while i < l:
        if A[i] > 0 and A[i] <=l:
            pos = A[i]-1
            if A[pos] != A[i]:
                A[pos],A[i] = A[i],A[pos]
                i-=1
        i+=1
    for i in range(len(A)):
        if A[i] != i+1:
            return i+1
    return l

Let me break this down for you.

• For each element, A[i] , we need to put it in A[A[i]-1].

So, let pos = A[i]-1, this is where we’ll store our A[i]. But we’ll lose the value stored at A[pos] ? So we store the value at A[pos] at current element A[i].

But the value at A[i] isn’t necessarily A[i]+1 ? So we need to process it again at this index, thus we do i=i-1.

Cool trick eh?