Find All Numbers Disappeared in an Array

Difficulty: Easy | Acceptance: 64.10% | Paid: No Topics: Array, Hash Table

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.

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

• Examples
• Constraints
• Approach 1: Hash Set
• Approach 2: Negation Marking
• Approach 3: Cyclic Sort

Examples

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Explanation: The number 5 does not appear in nums, and the number 6 does not appear in nums.

Input: nums = [1,1]
Output: [2]

Constraints

n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= n

Hash Set

Intuition Use a hash set to store all numbers seen in the array. Then iterate from 1 to n and check which numbers are missing from the set.

Steps

• Insert all elements of nums into a HashSet.
• Iterate from 1 to n (inclusive).
• If the current number is not in the set, add it to the result list.

from typing import List

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        num_set = set(nums)
        return [i for i in range(1, len(nums) + 1) if i not in num_set]

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses O(n) extra space for the set.

Negation Marking

Intuition Since all values are positive and within the range [1, n], we can use the input array itself as a marker by negating the value at the index corresponding to a number.

Steps

• Iterate through the array. For each number num, calculate its index idx = abs(num) - 1.
• Mark the number at idx as seen by making it negative (if it isn’t already).
• Iterate through the array again. If the value at index i is positive, it means the number i + 1 was never seen, so add it to the result.

from typing import List

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for num in nums:
            idx = abs(num) - 1
            if nums[idx] > 0:
                nums[idx] = -nums[idx]
        return [i + 1 for i, n in enumerate(nums) if n > 0]

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Modifies the input array in-place.

Cyclic Sort

Intuition Place each number in its correct position (index num - 1) by swapping. Once sorted, any index i that does not contain i + 1 indicates a missing number.

Steps

• Iterate through the array with index i.
• While nums[i] is not at its correct position (nums[i] != nums[nums[i] - 1]), swap it with the number at its target index.
• After the loop, iterate through the array. If nums[i] != i + 1, then i + 1 is missing.

from typing import List

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        i = 0
        n = len(nums)
        while i < n:
            correct_idx = nums[i] - 1
            if nums[i] != nums[correct_idx]:
                nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
            else:
                i += 1
        return [i + 1 for i in range(n) if nums[i] != i + 1]

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Modifies the input array in-place.