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.
