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

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