Convert the array to a set for O(1) lookups, then iterate through the range [1, n] and collect any number not found in the set. Simple and straightforward.
Use the array itself as a hash map. For each number, mark the value at its corresponding index as negative. After marking, any index that still has a positive value means that index + 1 is missing from the array.
""" 0448.1 - Find All Numbers Disappeared in an Array - Solution 1 - Hash Set """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
"""Find All Numbers Disappeared in an Array Function"""
num_set = set(nums)
return [i for i in range(1, len(nums) + 1) if i not in num_set]
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1])) # [5, 6]
print(Solution().findDisappearedNumbers([1, 1])) # [2]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0448.2 - Find All Numbers Disappeared in an Array - Solution 2 - In-Place Marking """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
"""Find All Numbers Disappeared in an Array Function"""
for num in nums:
index = abs(num) - 1
if nums[index] > 0:
nums[index] = -nums[index]
return [i + 1 for i in range(len(nums)) if nums[i] > 0]
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1])) # [5, 6]
print(Solution().findDisappearedNumbers([1, 1])) # [2]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()