# HelloKoding

Practical coding guides

# Smallest Missing Positive Integer

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
• Positive integer is a greater than zero number

## 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

SmallestMissingPositiveNumberBySorting.java

``````package com.hellokoding.algorithm;

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

SmallestMissingPositiveNumberByHashtable.java

``````package com.hellokoding.algorithm;

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