448. Find All Numbers Disappeared in An Array - Explanation

Description

You are given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Note: You can return the integers in any order.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]

Output: [5,6]

Example 2:

Input: nums = [1,1]

Output: [2]

Constraints:

1 <= nums[i] <= nums.length <= 100,000

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Hash Set

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        store = set(range(1, n + 1))

        for num in nums:
            store.discard(num)

        return list(store)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Boolean Array

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        mark = [False] * n

        for num in nums:
            mark[num - 1] = True

        res = []
        for i in range(1, n + 1):
            if not mark[i - 1]:
                res.append(i)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Sorting

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()

        res = []
        idx = 0
        for num in range(1, n + 1):
            while idx < n and nums[idx] < num:
                idx += 1
            if idx == n or nums[idx] > num:
                res.append(num)
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

4. Negative Marking

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for num in nums:
            i = abs(num) - 1
            nums[i] = -1 * abs(nums[i])

        res = []
        for i, num in enumerate(nums):
            if num > 0:
                res.append(i + 1)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since we modified the input array without using extra space.