Python Beginner Algorithms Tutorial

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

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¶

In :
# assert find_disappeared_numbers_in_array([1, 3, 4, 3]) == 


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.

In :
# 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¶

In :
# 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¶

In :
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¶

In :
assert find_disappeared_numbers_in_array([1, 3, 4, 3]) == 

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