In this article, you will learn to resolve the smallest missing positive integer problem by using sorting and hash table algorithms

## Problem

• Given an unsorted array of numbers `a`

• Write an algorithm to find the smallest missing positive integer in `a`

• A positive integer number is always greater than zero

## Example 1

• Input: [1, 3, 6, 4, 1, 2]

• Output: 5

## Example 2

• Input: [−1, −3, 5]

• Output: 1

## Hint

• The smallest positive integer is 1

## Approach 1: Sorting

• Sort the given array in ascending order

• Say `min=1` is smallest missing positive integer number. Iterate over the sorted array, increase `min` by 1 if `a[i] == min`

• Return `min` as the final result

``````import java.util.Arrays;

public class SmallestMissingPositiveNumberBySorting {
public static int findSmallest(int[] a) {
Arrays.sort(a);
int min = 1;

for (int i = 0; i < a.length; i++) {
if (min == a[i]) {
min++;
}
}

return min;
}

public static void main(String[] args) {
System.out.println(findSmallest(new int[]{1, 3, 6, 4, 1, 2}));
System.out.println(findSmallest(new int[]{-1, -3, 5}));
}
}
``````
• Output
``````5
1
``````
• Time complexity: O(nlogn) as `Arrays.sort(a)` takes nlogn time

• Space complexity: O(1)

## Approach 2: Hash table

• Add all positive numbers of the given array to a hash set

• Say `min=1` is smallest missing positive integer number. Keep increasing `min` by 1 if the hash set still contains `min`

• Return `min` as the final result

``````import java.util.Arrays;
import java.util.HashSet;

public class SmallestMissingPositiveNumberByHashtable {
public static int findSmallest(int[] a) {
HashSet<Integer> hashSet = new HashSet<>();

for (int value : a) {
if (value > 0) {
}
}

int min = 1;
while (hashSet.contains(min)) {
min++;
}

return min;
}

public static void main(String[] args) {
System.out.println(findSmallest(new int[]{1, 3, 6, 4, 1, 2}));
System.out.println(findSmallest(new int[]{-1, -3, 5}));
}
}
``````
• Output
``````5
1
``````
• Time complexity: O(n) as you iterate over the given array `n` times

• Space complexity: O(n) as you use a hash set to hold positive numbers