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) {
                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
Follow HelloKoding