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) {
                hashSet.add(value);
            }
        }

        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

Algorithm