# Find All Numbers Disappeared in an Array

## Question ([LC.448](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/#/description))

Given an array of integers where `1 ≤ a[i] ≤ n`, some elements appear twice and others appear once.\
Find all the elements of `[1, n]` inclusive that do not appear in this array.

## Example

```
I: [4,3,2,7,8,2,3,1]
O: []
```

## Analysis

The largest element in the array is less or equal than the size of the array. There possible frequencies 0, 1, or 2.

## Brute Force Approach

Use a hashtable to store each element and their frequencies. Return all keys/elements that have value 0.\
One pass to create the hashtable then a second pass to get the elements.\
Time O(n) Space O(n)

## Sorting Approach

Sorted the array first. Then do a linear scan with a for loop (and a while for the 2 case) and put the missing elements in the result list.\
Time O(nlgn) Space O(1)

## Linear Time?

The sorting approach didn't take advantage of the fact that there are only 3 possible frequencies.\
We are interested in the 0 case. Yep the 0 case. Have a copy of the array as a list. We can remove the elements by their indices and keep track of them???

We can use indices to store counts.

## Reference

this [blog post](http://blog.csdn.net/yutianzuijin/article/details/53861485)