You are given an integer array
arr
, write a program to return the
smallest missing positive integer.
Problem Note
- The array is unsorted.
- 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: arr[] = [5,1,7,3,9,2,4]
Output: 6
Explanation: In the above example, 6 and 8 are missing in the input array. But 6 is the smallest missing number. Hence, the output is 6.
Example 2
Input: arr[] = [5,8,3,6,2]
Output: 1
Explanation: In the above example, 1, 4, and 7 are missing in the input array. But 1 is the smallest missing number. Hence, the output is 1.
Example 3
Input: arr[] = [1,4,3,2]
Output: 5
Explanation: In the above example, no natural number is missing in between the input elements. So, we'll take the number just after the largest input element. Hence, the output is 5.