Find All Numbers Disappeared in an Array

Question (LC.448)

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