hardArrays & HashingPure DSA~35 min
Smallest Unissued Ticket Number
Tickets are numbered from 1 upward. Given the set of numbers currently issued (unsorted, possibly with gaps, duplicates, and out-of-range junk), find the smallest positive ticket number that has not yet been issued — in O(n) time and O(1) extra space.
Problem
Given an unsorted integer array nums, return the smallest positive integer that does not appear in it. You must run in O(n) time and use O(1) auxiliary space (you may modify nums in place).
Input
An integer array nums (may contain negatives, zeros, and duplicates).
Output
The smallest missing positive integer (≥ 1).
Constraints
- 1 ≤ n ≤ 1e5
- -2^31 ≤ nums[i] ≤ 2^31 - 1
Examples
Example 1
Input
[3,4,-1,1]
Output
2
1, 3, 4 are present; 2 is the smallest positive missing.
Example 2
Input
[7,8,9,11,12]
Output
1
No small positives present, so 1 is missing.