Missing Integer: Find the smallest positive integer that does not occur in a given sequence.

MissingInteger

Find the smallest positive integer that does not occur in a given sequence.

Problem

Write a function:

def solution(A)

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [−1,000,000..1,000,000].

Rohit’s Solution: Based on sorting of input array

def solution(A):
  B = [i for i in A if i > 0]
  if len(B) > 1:
      B = sorted(list(set(B)))
      if B[0] != 1:
          return 1
  elif len(B) == 1:
      if B[0] == 1:
          return 2
      else:
          return 1
  else:
      return 1
  for i in range(len(B) - 1):
      if B[i+1] - B[i] != 1:
          return B[i] + 1
      elif B[i+1] - B[i] == 1 and (i+1) == len(B)-1:
          return B[i+1] + 1

The idea is to:

(1) Sort the input array

(2) Capture differences between two consecutive numbers, if the difference is not equal to one return there with the appropriate value.

My Solution: Based on a counter variable

Detected time complexity: O(N) or O(N * log(N))

The idea is to maintain a counter with length equal to len(A) + 1

This counter is initialized to False and counter[0] initialized to True.

The n’th element of counter signifies () if the element was found in input array A or not.

We iterate of A to update our counter.

Then to return an output, we iterate over A again to detect the first False flag and return it’s index.

Code

def solution(A):
  if len(A) == 1:
      if A[0] == 1:
          return 2
      else:
          return 1
  else:
      B = [False for i in range(len(A) + 1)]
      B[0] = True 
      for i in A:
          if i < len(B) and i > 0:
              B[i] = True 
          
      for i in range(len(B)):
          if B[i] == False:
              return i
      return len(B)

Tags: Algorithms,Technology,Python,