💬 Discord
Sign In
NeetCode #54LC-448EasyArrays & Hashing
← Back to All Problems

#54 · #448 · Find All Numbers Disappeared in an Array(找到所有数组中消失的数字)

📌 Problem Statement & Constraints

Given an array nums of n integers where each element is in the range [1, n], return an array of all the integers in [1, n] that do not appear in nums. Constraints: n == nums.length, 1 <= n <= 10^5. Solve it in O(n) time with O(1) auxiliary space (the output array does not count).

💡 Core Algorithmic Approaches

  1. Because every value lies in [1, n], the value v can serve as an index into the array itself: v - 1.
  2. Marking pass: for each value, take the absolute value (it may already have been negated), then negate nums[v - 1] to record that v was seen.
  3. Collecting pass: any index i whose value is still positive means i + 1 was never marked, so i + 1 is missing.
  4. Using abs on the read is essential, because a previously negated slot would otherwise give a negative index.

💻 Benchmark Python3 Implementation

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n):
            idx = abs(nums[i]) - 1         # abs is required: the slot may be negated
            if nums[idx] > 0:
                nums[idx] = -nums[idx]     # mark as seen
        res = []
        for i in range(n):
            if nums[i] > 0:                # never marked -> i+1 is missing
                res.append(i + 1)
        return res


# Cyclic-sort variant: place each value at its home index first
class Solution2:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        i = 0
        while i < n:
            home = nums[i] - 1
            if nums[i] != nums[home]:      # swap into the correct slot
                nums[i], nums[home] = nums[home], nums[i]
            else:
                i += 1
        return [i + 1 for i in range(n) if nums[i] != i + 1]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): two passes, with O(1) amortised work per element. The cyclic-sort variant is also O(n) amortised, since each swap places one value permanently.
💾 Space Complexity
O(1) auxiliary: the input array is used as the marking structure. A hash-set solution would be O(n) space.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting abs in the marking pass: once a slot is negated, reading it directly yields a negative index, which in Python silently wraps around and corrupts the marking.
  • Marking with nums[idx] = -1 unconditionally: it would still work for this problem, but negating is the safer idiom because it preserves the magnitude for the second pass.
  • Using a set: O(n) space, violating the stated O(1) requirement.
  • Assuming the array is a permutation: it is not, which is exactly why some numbers are missing.