Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums. You must write an algorithm that runs in O(n) time and uses only constant extra space.
Java
Find All Numbers Disappeared in an Array
Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums. You must write an algorithm that runs in O(n) time and uses only constant extra space.
Example 1:
Input: [4,3,2,7,8,2,3,1]
Output: [5,6]
Input
arr =[4,3,2,7,8,2,3,1]
Array has 8 elements. Find all numbers from 1 to 8 that are missing.
Phase 1: Marking Present Numbers
Current Index
Target Index
Negative (Present)
Positive (Missing)
Array (index i represents number i+1)
4
[0](1)
3
[1](2)
2
[2](3)
7
[3](4)
8
[4](5)
2
[5](6)
3
[6](7)
1
[7](8)
Algorithm: Use array indices to track presence
- Phase 1: For each value v, negate nums[|v| - 1] to mark v as present
- Phase 2: Indices with positive values represent missing numbers