Codility ‘MissingInteger’ Solution

Short Problem Definition:

Find the minimal positive integer not occurring in a given sequence.

Link

MissingInteger

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

You only need to consider the first (N) positive integers. In this specification 0 does not count as a valid candidate! Any value that is below 1 or above N can be ignored.

Solution:
def solution(A):
    seen = [False] * len(A)
    for value in A:
        if 0 < value <= len(A):
            seen[value-1] = True

    for idx in xrange(len(seen)):
        if seen[idx] == False:
            return idx + 1

    return len(A)+1

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • FatTailBlackSwan

    Value can be any signed (32bit) int, no?

  • FatTailBlackSwan

    Only checking up to N is the key insight. Thank you!

  • han

    I have implemented slightly different logic which might be a bit faster:

    def solution(A):
    newA= [x+1 for x in A]+[1]
    diff=set(newA)-set(A)
    diff=filter(lambda a: a>0, diff)
    #diff=filter(lambda a: a>0, diff)
    result=min(diff)
    return result