Find Smallest Missing Positive Integer
EasyPractice library · +10 XPtwo pointersbinary searcharrays
Given a sorted array of integers (possibly containing duplicates, negatives, and zeros), find the smallest positive integer (greater than 0) that is missing from the array. If all positive integers from 1 up to N are present, the answer is N+1.
Input
The first line contains an integer N, the size of the array. The second line contains N space-separated integers representing the array elements.
Output
Print a single integer: the smallest missing positive integer.
Constraints
1 <= N <= 1000. Array elements are between -1000 and 1000.
Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
5 1 2 0 4 5
Output
3
The positive integers are 1, 2, 4, 5. The smallest missing positive integer is 3.
Example 2
Input
7 -2 -1 0 1 2 3 4
Output
5
The positive integers are 1, 2, 3, 4. The smallest missing positive integer is 5.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 2 0 4 5
Example 2 input
7 -2 -1 0 1 2 3 4