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

• A positive integer number is greater than zero

### Example 1

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

• Output: 5

### Example 2

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

• Output: 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

``````
``````
• 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

``````
``````
• 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