Given an array of integers where 1 ≤ a[i] ≤ *n* (*n* = size of array), some elements appear twice and others appear once.

Find all the elements of `[1, `

inclusive that do not appear in this array.*n*]

**Could you do it without extra space and in O( n) runtime?** You may assume the returned list does not count as extra space.

**Example:**

Input:[4,3,2,7,8,2,3,1]Output:[5,6]

The intuition behind using a hash map is pretty clear in this case. We are given that the array would be of size `N`

and it should contain numbers from `1`

to `N`

. However, some of the numbers are missing. All we have to do is keep track of which numbers we encounter in the array and then iterate from *1 …N1⋯N* and check which numbers did not appear in the hash table. Those will be our missing numbers.

But wait, that needs `O(N)`

extra space to maintain the `HashMap`

.

We definitely need to keep track of all the `unique`

numbers that appear in the array. However, we don’t want to use any extra space for it. Here we can use the

used in First Missing Positive number in an Array**in place hashing technique**

Walk along with the array. Change the sign of a

^{th}element if you meet a number`a`

. Be careful with duplicates: do sign change only once. Use`index 0`

to save information about the presence of a number`n`

since index`n`

is not available.Walk again along with the array. Return the index of the first positive element.

If

`nums[0] > 0`

return`n`

.

**Algorithm**

- Iterate over the input array one element at a time.
- For each element
`nums[i]`

, mark the element at the corresponding location negative if it’s not already marked so i.e.

. Use*nums*[*nums*[*i*]−1]×−1`nums[0]`

position to track for the`n'`

number. As we are interested to find the missing numbers between^{th}`1 to N`

only. And array indices are from`0 to n-1`

. So we can use the`0'`

location to track the presence of^{th}`n'`

number in the array.^{th} - Now, loop over numbers from
`1⋯N`

, and for each number check if`nums[i]`

is negative. If it is negative, that means we’ve seen this number somewhere in the array. - Add all the numbers to the resultant array which don’t have their corresponding locations marked as negative in the original array.
- Add the
`n'`

number in the array if^{th}`nums[0] > 0`

```
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList<>();
if(nums == null || nums.length == 0){
return result;
}
int n = nums.length;
for(int i = 0 ; i < n ; i++){
int k = Math.abs(nums[i]);
if(k == n){
nums[0] = - Math.abs(nums[0]);
}else{
nums[k] = - Math.abs(nums[k]);
}
}
for(int i = 1 ; i < n ; i++){
if(nums[i] > 0){
result.add(i);
}
}
if(nums[0] > 0){
result.add(n);
}
return result;
}
}
```

**Complexity Analysis**

**Time Complexity :**`O(N)`

**Space Complexity :**`O(1)`

since we are reusing the input array itself as a hash table and the space occupied by the output array doesn’t count toward the space complexity of the algorithm.

Categories: Array