Cyclic Sort
LC #448Easy
Find All Numbers Disappeared in an Array
Cyclic Sort
AmazonGoogleProblem
Given an array nums of n integers where each element is in the range [1, n], some elements appear twice and some appear once. Find all the integers in [1, n] that do not appear in nums. Example: [4,3,2,7,8,2,3,1] → [5,6]. Must be O(n) time and O(1) extra space (the output doesn't count).
arraycyclic-sort
Constraints
- ›n == nums.length
- ›1 ≤ n ≤ 10⁵
- ›1 ≤ nums[i] ≤ n
- ›O(1) extra space (excluding output)
Example
Input
nums = [4, 3, 2, 7, 8, 2, 3, 1]Output
[5, 6]Why
n=8, range [1,8]. Numbers 5 and 6 do not appear