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.
30:00
Java
Find All Numbers Disappeared in an Array
easy
Topics
Companies
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]
Constraints:
n==nums.length
1≤n≤105
1≤nums[i]≤n
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