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.
# 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.
# 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.
# 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:
n be the number of elements in the input list assigned to the variable
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.
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)
assert find_disappeared_numbers_in_array([1, 3, 4, 3]) == 
assert find_disappeared_numbers_in_array([5, 6, 1, 5, 6, 1]) == [2, 3, 4]