Smallest Positive Missing Number (Solution)

Problem Statement

Given an array containing both positive and negative numbers, find the smallest positive number excluded from the array.

Sample Test Cases

Input 1: a = [2, 3, 7, 6, 8, -1, -10, 15]
Output 1: 1
Explanation 1: 1 is the smallest positive integer missing from the array.

Input 2: a = [2, 3, -7, 6, 8, 1, -10, 15]
Output 2: 4
Explanation 2: 4 is the smallest positive integer missing from the array.

Approach 1: Looping Over Positive Integers

We can solve the problem naively by looping over all the positive integers and checking if each of them is present in the array or not. Whenever a number is not found in the array, we return it and break the algorithm.

C++ Code

int getMEX(vector < int > & a) {
  bool found = false;
  for (int i = 1;; i++) {
    found = false;
    for (auto x: a) {
      if (x == i) {
        found = true;
        break;
      }
    }
    if (!found) {
      return i;
    }
  }
}

Java Code

public static int getMEX(int[] a) {
  boolean found = false;
  for (int i = 1;; i++) {
    found = false;
    for (int j = 0; j < a.length; j++) {
      int x = a[j];
      if (x == i) {
        found = true;
        break;
      }
    }
    if (!found) {
      return i;
    }
  }
}

Python Code

def getMEX(a):
    found = False
    n = len(a)
    for i in range(1, n + 2):
        found = False
        for j in range(n):
            if a[j] == i:
                found = True
                break
        if found == False:
            return i

Complexity Analysis

• Time Complexity: O(n * n)
• Space Complexity: O(1)

Approach 2: Hashing Method

We can solve this problem in linear time by using hashing. We loop over all the positive numbers, and check if it is present in the array or not by using a lookup table or hash map in O(1) time. The first element not found in the array will be the answer.

C++ Implementation

int getMEX(vector < int > & a) {
  int n = a.size();
  unordered_set < int > hash(a.begin(), a.end());
  for (int i = 1; i <= n + 1; i++) {
    if (hash.find(i) == hash.end()) {
      return i;
    }
  }
}

Java Implementation

public static int getMEX(int[] a) {
  int n = a.length;
  HashSet < Integer > hash = new HashSet < Integer > ();
  for (int i = 0; i < n; i++) {
    hash.add(a[i]);
  }
  for (int i = 1; i <= n + 1; i++) {
    if (!hash.contains(i)) {
      return i;
    }
  }
  return -1;
}

Python Implementation

def getMEX(a):
    n = len(a)
    b = a
    hash = set(b)
    for i in range(1, n + 2):
        if i not in hash:
            return i

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Approach 3

The algorithm is described as follows:

• Move all the non-positive numbers to the left side of the array and separate out the positive numbers. After applying this function, all the nonpositive numbers in the array must appear before any positive number in the array.
• We now start iterating on the array from the index which has the first positive element. For each element ele, to mark that it is present in the array, we change the value at index ele to its negative. Then, we again iterate on the array and return the first index with a positive value.

C++ Implementation

int distribute(int a[], int n) {
  int j = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] <= 0) {
      swap(a[i], a[j]);
      j++;
    }
  }
  return j;
}
int getMEXUtil(int a[], int till) {
  for (int i = 0; i < till; i++) {
    if (abs(a[i]) - 1 < till && a[abs(a[i]) - 1] > 0) {
      a[abs(a[i]) - 1] *= (-1);
    }
  }
  for (int i = 0; i < till; i++) {
    if (a[i] > 0) {
      return i + 1;
    }
  }
  return till + 1;
}
int getMEX(int a[], int n) {
  int moved = distribute(a, n);
  return getMEXUtil(a + moved, n - moved);
}

Java Implementation

public static int distribute(int a[], int n) {
  int j = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] <= 0) {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
      j++;
    }
  }
  return j;
}
public static int getMEXUtil(int a[], int till) {
  for (int i = 0; i < till; i++) {
    if (Math.abs(a[i]) - 1 < till && a[Math.abs(a[i]) - 1] > 0) {
      a[Math.abs(a[i]) - 1] *= (-1);
    }
  }
  for (int i = 0; i < till; i++) {
    if (a[i] > 0) {
      return i + 1;
    }
  }
  return till + 1;
}
public static int getMEX(int a[], int n) {
  int moved = distribute(a, n);
  int[] aCopy = new int[n - moved];
  int j = 0;
  for (int i = moved; i < n; i++) {
    aCopy[j] = a[i];
    j++;
  }
  return getMEXUtil(aCopy, n - moved);
}

Python Implementation

def distribute(a, n):
    j = 0
    for i in range(n):
        if a[i] <= 0:
            temp = a[i]
            a[i] = a[j]
            a[j] = temp
            j += 1
    return j


def getMEXUtil(a, n):
    for i in range(n):
        x = abs(a[i])
        if x - 1 < n and a[x - 1] > 0:
            a[x - 1] *= -1
    for i in range(n):
        if a[i] > 0:
            return i + 1
    return n + 1


def getMEX(a, n):
    moved = distribute(a, n)
    return getMEXUtil(a[moved:], n - moved)

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Approach 4

We can solve this problem by making an auxiliary array of size the same as that of our given array. Now we traverse our original array, and whenever we find a positive value in the array, we update the index equal to that value with 1. Then we make another traversal through the auxiliary array and return the index + 1  of the first 0 encountered.

C++ Code

int getMEX(vector < int > & a, int n) {
  vector < bool > found(n + 2, false);
  for (auto x: a) {
    if (x > 0 && x <= n) {
      found[x] = true;
    }
  }
  for (int i = 1; i <= n + 1; i++) {
    if (!found[i]) {
      return i;
    }
  }
  return n + 1;
}

Java Code

public static int getMEX(int[] a, int n) {
  boolean[] found = new boolean[n + 2];
  for (int x: a) {
    if (x > 0 && x <= n) {
      found[x] = true;
    }
  }
  for (int i = 1; i <= n + 1; i++) {
    if (!found[i]) {
      return i;
    }
  }
  return n + 1;
}

Python Code

def getMEX(a, n):
    found = [False] * (n + 2)
    for i in range(n):
        if a[i] > 0 and a[i] <= n:
            found[a[i]] = True
    for i in range(1, n + 2):
        if found[i] == False:
            return i
    return n + 1

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Approach 5:

The algorithm is described as follows:

• If 1 is not present in the array, return 1.
• Traverse the array and change every element less than 1 or greater than n to 1.
• Traverse the array again and for each element a[i], update it to a[(a[i] – 1) % n] += n.
• Again traverse the array and return the first index which has a value less than or equal to n. If not found, return n + 1.

C++ Implementation

int getMEX(vector < int > & a, int n) {
  bool ok = false;
  for (int i = 0; i < n; i++) {
    ok |= (a[i] == 1);
  }
  if (!ok) {
    return 1;
  }
  for (auto & x: a) {
    if (x <= 0 || x > n) {
      x = 1;
    }
  }
  for (int i = 0; i < n; i++) {
    a[((a[i] - 1) % n + n) % n] += n;
  }
  int result = n + 1;
  for (int i = 0; i < n; i++) {
    if (a[i] <= n) {
      result = i + 1;
      break;
    }
  }
  return result;
}

Java Implementation

public static int getMEX(int[] a, int n) {
  boolean ok = false;
  for (int i = 0; i < n; i++) {
    ok |= (a[i] == 1);
  }
  if (!ok) {
    return 1;
  }
  for (int i = 0; i < n; i++) {
    if (a[i] <= 0 || a[i] > n) {
      a[i] = 1;
    }
  }
  for (int i = 0; i < n; i++) {
    a[((a[i] - 1) % n + n) % n] += n;
  }
  int result = n + 1;
  for (int i = 0; i < n; i++) {
    if (a[i] <= n) {
      result = i + 1;
      break;
    }
  }
  return result;
}

Python Implementation

def getMEX(a, n):
    if 1 not in a:
        return 1
    for i in range(n):
        if a[i] <= 0 or a[i] > n:
            a[i] = 1
    for i in range(n):
        a[((a[i] - 1) % n + n) % n] += n
    for i in range(n):
        if a[i] <= n:
            return i + 1
    return n + 1

Complexity Analysis:

• Time Complexity: O(n)
• Space Complexity: O(1)

Approach 6

The algorithm is described as follows:

• Traverse the array, and while a[i] > 1 and a[i] <= n and a[i] != a[a[i] – 1], conditions are true, swap a[i] with a[a[i] – 1].
• Traverse the array again, and return the first index where a[i] != i + 1. If such an index is not found, return n + 1.

C++ Implementation For The Approach

int getMEX(vector < int > & a, int n) {
  for (int i = 0; i < n; i++) {
    while (a[i] > 0 && a[i] <= n && a[i] != a[a[i] - 1]) {
      swap(a[i], a[a[i] - 1]);
    }
  }
  int result = n + 1;
  for (int i = 1; i <= n; i++) {
    if (i != a[i - 1]) {
      result = i;
      break;
    }
  }
  return result;
}

Java Implementation For The Approach

public static int getMEX(int[] a, int n) {
  for (int i = 0; i < n; i++) {
    while (a[i] > 0 && a[i] <= n && (a[i] != a[a[i] - 1])) {
      int temp = a[a[i] - 1];
      a[a[i] - 1] = a[i];
      a[i] = temp;
    }
  }
  int result = n + 1;
  for (int i = 1; i <= n; i++) {
    if (i != a[i - 1]) {
      result = i;
      break;
    }
  }
  return result;
}

Python Implementation For The Approach

def getMEX(a, n):
    for i in range(n):
        while a[i] > 0 and a[i] <= n and a[i] != a[a[i] - 1]:
            temp = a[a[i] - 1]
            a[a[i] - 1] = a[i]
            a[i] = temp
    for i in range(n):
        if a[i] != (i + 1):
            return i + 1
    return n + 1

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

FAQs

Q. Can this problem be solved by using sorting?
A. Yes, this problem can be solved using standard sorting algorithms, albeit in O(nlogn).

Q. What is the complexity of the lookup operations of hashmap in approach 2?
A. The lookup time complexity of hashmaps is amortized O(1) with the use of a good hash function.