You are given an integer array, write a program to return the smallest missing positive integer.

Problem Note

  • The array is unsorted
  • In other words, you need to return the smallest natural number that is not in the list
  • You are expected to solve this in O(n) time using O(1) extra space

Example 1

Input: A[] = [5,1,7,3,9,2,4]
Output: 6

Example 2

Input: A[] = [5,8,3,6,2]
Output: 1

Example 3

Input: A[] = [1,4,3,2]
Output: 5