Codility ‘MissingInteger’ Solution

I came across another interesting coding problem on Codility and wanted to share my learnings.

Problem

Find the smallest positive integer (>0) not occurring in a given sequence. Link to the full problem (Lesson 4 — Counting Elements).

Solution in Python

I’ve scored 100% for this solution

def solution(A):
    num_set = set(A)
    min_num = 1
    while min_num in num_set:
        min_num+=1
    return min_num
#testcase1, expect 5
solution([1, 3, 6, -4, 1, 2,-3])
#testcase2, expect 4
solution([1, 2, 3])
#testcase3, expect 1
solution([-2, -4])

• I created a set of array A to avoid re-checking duplicates.
• I have set min_num = 1. If 1 is not found in the array, it is returned immediately as it’s the lowest possible positive integer. As seen in test case #3, we will return 1 straight.
• If 1 is found in the array, then we will iteratively add 1 and check if it’s in the num_set. This will ensure that we return the lowest possible number.
• The worst case time-complexity would be O(n) if we have to iterate to the end of the list, as seen in test case #2.

Hope it helps! :)

If you found this article helpful, I would really appreciate if you could follow my account and give this article a clap! Thank you!! :D