Smallest positive integer

SmallestPositive.md

Algorithms

Problem #1

/*
 * Write a function:
 * function 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.
 * 1 1 2 3 4 6 
 * 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].
*/

Solution

Pseudocode

1. Sort A
2. I=1, X=0, N=lenght(A)
3. While (I <= N) repeat
    3.1. if I not in A 
            then
                X=I
                return X
            else
                I+1
    End step 3.1
4. End step 3
5. X=I+1

Explanation

Step 1. => Sort array takes O(NlogN) in worst case.

Step 2. => Declare and init flags.

Step 3. => Loop for each element in array given. Takes O(N) in worst case.

Step 3.1. => Check if array contain I then return X=I else increment I.

Step 4. => End loop.

Step 5. => Increment X

Finally O(NlogN) + O(N)

Examples

Python 3

def solution(arr: list) -> int():
    """
    Returns the smallest positive integer (greater than 0) that does not occur in arr.
    """
    arr.sort()
    N = len(arr)
    X = 0
    for i in range(1, N+1):
        if i not in arr:
            return i
        X = i
    return X + 1
    
print(solution([1, 3, 6, 4, 1, 2]))
print(solution([1, 2, 3]))
print(solution([-1, -3]))

JavaScript ESX

/**
 * Returns the smallest positive integer (greater than 0) that does not occur in A.
 * @param {Array} arr List of integers
 */
function solution (arr) {
  arr.sort((a, b) => a - b) // O(NlogN)
  let x = 0
  for (let i = 1; i <= arr.length; i++) { // O(N)
    if (!arr.includes(i)) return i
    else x = i
  }
  return ++x
}

console.log(solution([1, 3, 6, 4, 1, 2]))
console.log(solution([1, 2, 3]))
console.log(solution([-1, -3]))