# Find All Numbers Disappeared in an Array (via Leetcode)

- March 28, 2020
- Key Terms: functions, loops, sets

**Problem setup**

This problem is on Leetcode.

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, n] inclusive that do not appear in this array.

### Test Cases¶

```
# assert find_disappeared_numbers_in_array([1, 3, 4, 3]) == [2]
```

In this test case, the size of the array is 4, assigned to `n`

. All elements of `[1, n]`

would be `[1, 2, 3, 4]`

. However, the input list does not contain `2`

. Therefore, this test case should return 2.

```
# assert find_disappeared_numbers_in_array([5, 6, 1, 5, 6, 1]) == [2, 3, 4]
```

In this test case, the the size of the array is 6. All elements of `[1, n]`

would be `[1, 2, 3, 4, 5, 6]`

. However, the array doesn't contain `[2, 3, 4]`

and so our function should return that.

### Pseudocode¶

```
# build a python set of all numbers from i to n with n being the size of the array.
# iterate over input list
# if item in set:
# pop item out of set
# return: convert set to a list
```

**Explanation of space and time complexity**:

Let `n`

be the number of elements in the input list assigned to the variable `nums`

.

I iterate over `n`

and therefore it's an O(n) time complexity. There a is another O(1) check for membership in the set that is done O(n) times. Total time complexity is O(2n). The 2 is negligent so most people say this is just O(n) time complexity.

I initially create a Python set of values from 1 to the value of `n`

. Therefore, this is an O(n) space complexity.

Here is a great resource on time complexity operations in Python.

### Code¶

```
def find_disappeared_numbers_in_array(nums):
length_nums = len(nums)
all_numbers_set = set(range(1, length_nums + 1))
for num in nums:
if num in all_numbers_set:
all_numbers_set.remove(num)
return list(all_numbers_set)
```

### Verify Test Cases¶

```
assert find_disappeared_numbers_in_array([1, 3, 4, 3]) == [2]
```

```
assert find_disappeared_numbers_in_array([5, 6, 1, 5, 6, 1]) == [2, 3, 4]
```