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