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.
Example:
Input: [4,3,2,7,8,2,3,1]Output: [5,6]
Source
def disappeared_numbers(nums):
"""
Time Complexity O(n)
Space Complexity O(n)
"""
buff_set = set(nums)
missing_nums = []
for number in range(1, len(nums)+1):
if number not in buff_set:
missing_nums.append(number)
return missing_nums
def disappeared_numbers(nums):
"""one line version of above solution."""
return list(set(range(1, len(nums)+1)) - set(nums))
nums = [4,3,2,7,8,2,3,1]
disappeared_numbers(nums)
[5, 6]
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
### First, let's imagine this problem but with 0 <= a[i] <= n
def disappeared_numbers(nums):
"""We match the integers in the table and their indexes
Time Complexity O(n)
Space Complexity O(1)
"""
for i in range(len(nums)):
index = abs(nums[i]) # we find the number that nums[i] points to
nums[index] = - abs(nums[index]) # and we mark it as negative (now, the number AT "index" is <= 0)
# # which tell us that the number "index" was spotted in nums
# # abs() is to avoid being tricked by duplicates
return [i for i, n in enumerate(nums) if n > 0] # only the remaining positive elements
# didn't appear in the values of nums
nums = [3,2,1,6,7,1,2,0]
print(set(sorted(nums)), " --> ", disappeared_numbers(nums))
{0, 1, 2, 3, 6, 7} --> [4, 5]
nums = [3,2,1,6,7,1,2,1]
print(set(sorted(nums)), " --> ", disappeared_numbers(nums))
{1, 2, 3, 6, 7} --> [0, 4, 5]
nums = [4,3,2,7,7,2,3,0]
print(set(sorted(nums)), " --> ", disappeared_numbers(nums))
{0, 2, 3, 4, 7} --> [1, 5, 6]
### Now we just need to adjust +/-1 since 1 <= a[i] <= n
def disappeared_numbers(nums):
"""Same as above, but adjusted for the fact that 1 <= a[i] <= n"""
for i in range(len(nums)):
index = abs(nums[i]) - 1
nums[index] = - abs(nums[index])
return [i+1 for i, n in enumerate(nums) if n > 0]
def disappeared_numbers(nums):
"""variation of above"""
nums = [0] + nums # this prevents having to do +/- 1 later on
for i in range(len(nums)):
index = abs(nums[i])
nums[index] = -abs(nums[index])
return [i for i, n in enumerate(nums) if n > 0]
nums = [4,3,2,7,8,2,3,1]
disappeared_numbers(nums)
[5, 6]