Find All Numbers Disappeared in an Array — Index Negation O(n) O(1) [Meta Easy]

Problem Statement#

Given an array nums of n integers where each integer is in the range [1, n], return an array of all integers in [1, n] that do not appear in nums.

You must do it without using any extra space (the output array does not count as extra space) and in O(n) runtime.

Example 1:

Input:  nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [5, 6]
Explanation: 5 and 6 are the only integers in [1..8] not present in the array.

Example 2:

Input:  nums = [1, 1]
Output: [2]
Explanation: 2 is the only integer in [1..2] not present in the array.

Constraints:

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

Why This Problem Matters#

LeetCode 448 appears regularly in Meta, Google, and Amazon phone screens for one specific reason: it is a clean test of whether you know the index-as-a-hash-key pattern. The problem looks trivially easy — just use a set, check which numbers are missing. Any junior developer can write that in 30 seconds. But the problem explicitly says O(1) extra space. No set. No dictionary. No frequency array.

That constraint is the entire point. It forces you to think about the array itself as a data structure. The values are in the range [1, n] and the indices are in the range [0, n-1]. That is not a coincidence — it is an invitation. When the value domain and the index domain are aligned like this, you can encode information directly into the array without needing any external storage.

The index-as-a-hash-key pattern appears in a cluster of problems that are deceptively simple on the surface but reveal your data-structure intuition at depth: Find the Duplicate Number (LC 287), First Missing Positive (LC 41), and Cyclic Sort problems all rely on the same insight. Solving LC 448 properly is the entry point to this entire family.

Interviewers also use this problem to test a secondary skill: comfort with in-place mutation. Many candidates who understand the concept still flinch when asked to modify the input array. Being able to talk through why the mutation is safe — and how to recover the original state if needed — is exactly the kind of reasoning that separates candidates who pass from candidates who stall.

The Core Insight — Index Marking via Negation#

Before writing a single line of code, let's build the intuition from scratch.

You have an array of length n containing integers in [1, n]. Some numbers appear twice; some numbers are absent. You need to find the absent ones.

The key observation: index i corresponds to the number i + 1. If number k exists in the array, index k - 1 is its "home" index.

Here is the trick: walk through the array and for each value you encounter, visit its home index and negate the value there. This is like placing a checkmark at that index — you are saying "the number k exists." Crucially, you are encoding this information inside the array itself using the sign of the element.

Why negation? Because:

1. It is reversible — you can recover the original value with abs().
2. It does not change the magnitude, only the sign, so future reads of this index still correctly identify the home index (via abs(nums[i]) - 1).
3. After the full pass, any index that still holds a positive value was never visited — meaning the number index + 1 was never present in the array.

This is O(n) time (one pass to mark, one pass to collect) and O(1) extra space (all mutations happen inside nums).

Visual Dry Run#

Let's trace nums = [4, 3, 2, 7, 8, 2, 3, 1] step by step.

Starting state:

Pass 1 — mark home indices by negation:

State after Pass 1:

Pass 2 — collect indices still holding positive values:

• Index 4: value = 8, still positive → number 5 is missing
• Index 5: value = 2, still positive → number 6 is missing

Output: [5, 6] — correct.

Notice why step i=5 (value 2) did not double-negate: we check if nums[home] > 0 before negating. If it is already negative, the number was already marked. This prevents corrupting indices that were visited more than once due to duplicates.

Common Mistakes#

These are errors real candidates make in real interviews — not theoretical edge cases, but live thinking errors under pressure.

Mistake 1: Negating without the "already negative" guard.

The most common bug is writing the marking step as an unconditional negation:

# WRONG — will double-negate and undo the mark
nums[idx] = -nums[idx]

When a number appears twice (like 2 and 3 in the example above), its home index gets visited twice. Without the guard if nums[idx] > 0, the second visit re-negates the value back to positive, making it look like the number was never seen. The fix is always to check the sign first and only negate if the value is still positive.

Mistake 2: Using the raw current value instead of abs() to compute the home index.

After you start negating values in the array, you may visit an index that already holds a negative number. If you compute the home index as nums[i] - 1 instead of abs(nums[i]) - 1, you get a negative index — an out-of-bounds error. Every single read of a value to compute a home index must go through abs().

Mistake 3: Off-by-one errors on the index-to-number mapping.

The array is zero-indexed but the numbers are in [1, n]. The mapping is: value k lives at home index k - 1. Equivalently, if index i is still positive after marking, the missing number is i + 1. Candidates flip this in both directions: some use nums[i] - 0 (forget the -1 offset) and some report i instead of i + 1. Trace through one small example before submitting — this mistake is invisible until you test with a concrete case.

Mistake 4: Reaching for a set when the constraint says O(1) space.

In a real interview, writing the hashset solution when the problem specifies O(1) extra space is a red flag — it signals you did not read the constraints carefully, or you defaulted to a safe answer under pressure instead of engaging with the hard part. Even if you say "let me start with the hashset and optimize," make sure you can actually complete the optimization. Interviewers will always ask: "Can you do this without extra space?"

Mistake 5: Forgetting that duplicates mean a number appears at most twice, not that it appears exactly twice.

The constraint says 1 <= nums[i] <= n with n elements. A number can appear 0, 1, 2, or more times. The algorithm handles all these cases correctly, but candidates sometimes reason about it as if duplicates are always pairs. Make sure your explanation covers the general case.

Solutions#

Approach 1 — HashSet (O(n) time, O(n) space)#

The straightforward approach: put every number into a set, then check which numbers in [1, n] are absent. This is the solution to reach for first when the O(1) space constraint is not given (or when the interviewer says to start simple).

Python

from typing import List
 
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        # Store every number we've seen in a set — O(n) space
        seen = set(nums)
 
        result = []
        # Check each number in [1, n] — if it's not in the set, it's missing
        for num in range(1, len(nums) + 1):
            if num not in seen:
                result.append(num)
 
        return result

JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function findDisappearedNumbers(nums) {
    // Build a set of all values present in the array — O(n) space
    const seen = new Set(nums);
 
    const result = [];
    // Check each integer in [1, n]; add it to result if it wasn't seen
    for (let num = 1; num <= nums.length; num++) {
        if (!seen.has(num)) {
            result.push(num);
        }
    }
 
    return result;
}

Approach 2 — Index Negation (O(n) time, O(1) extra space) — Optimal#

Use the sign of each element as a boolean flag. For each number seen, negate the value at its corresponding home index. After marking, any index still holding a positive value corresponds to a missing number.

Python

from typing import List
 
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        # --- Pass 1: mark home indices of numbers we've seen ---
        for n in nums:
            # Use abs() because nums[i] may already be negative from a prior mark
            home_idx = abs(n) - 1  # value k lives at index k-1
 
            # Only negate if still positive — guard against double-negation on duplicates
            if nums[home_idx] > 0:
                nums[home_idx] = -nums[home_idx]
 
        # --- Pass 2: collect indices still holding positive values ---
        result = []
        for i, val in enumerate(nums):
            # A positive value at index i means number (i+1) was never seen
            if val > 0:
                result.append(i + 1)  # convert 0-based index back to 1-based number
 
        return result

JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function findDisappearedNumbers(nums) {
    // --- Pass 1: mark each number's home index using sign negation ---
    for (let i = 0; i < nums.length; i++) {
        // abs() is essential — the value at index i may already be negative
        const homeIdx = Math.abs(nums[i]) - 1;  // value k maps to index k-1
 
        // Guard: only negate if positive; prevents undoing a mark on duplicates
        if (nums[homeIdx] > 0) {
            nums[homeIdx] = -nums[homeIdx];
        }
    }
 
    // --- Pass 2: any index still positive means that number never appeared ---
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            result.push(i + 1);  // 0-based index i → 1-based missing number i+1
        }
    }
 
    return result;
}

Complexity Analysis#

On the constant factor: Both approaches make two linear passes in the worst case — the negation approach is not slower in practice. The hashset approach has higher constant-factor overhead due to hash computation and memory allocation.

On "O(1) extra space": The problem says the output array does not count. This is standard in problems where the output is unavoidably proportional to n. The constraint targets auxiliary data structures like frequency arrays, hashmaps, and sets — not the return value itself.

Why two passes instead of one? You could attempt a single pass but you would need to handle forward references: when processing index i, you might need to mark an index j > i that has not been reached yet. The negation approach handles this correctly because you always use abs() — so a future mark on index j will not be lost when you later visit j. The two-pass structure is clean, correct, and easy to reason about.

Follow-up Questions#

These are the escalation questions that appear in real FAANG interviews after you solve the base problem.

Q1: How would you restore the array to its original state after finding the missing numbers?

After collecting the result, do a second pass and negate every remaining negative number back to positive: nums[i] = abs(nums[i]) for all i. This restores the original values. This is a common follow-up at companies like Google that emphasize clean APIs — the caller passed you an array; should you silently mutate it? The correct engineering answer is: mutate during computation for O(1) space, then restore before returning if the function contract requires it.

Q2: What if the constraint changes — numbers can be in [1, 2n] instead of [1, n]?

Now the index domain and value domain are no longer aligned. The negation trick breaks. Fall back to the hashset O(n) space approach, or sort the array and check for gaps in O(n log n) time / O(1) extra space. This follow-up tests whether you understand why the negation trick works — if you do, you will immediately see that misaligned domains break the assumption.

Q3: Find the duplicate numbers instead of the missing numbers. How does the approach change?

Instead of collecting indices with positive values after marking, collect the index every time you try to negate a value that is already negative — that means the number corresponding to that index was seen before. This is LeetCode 442 (Find All Duplicates in an Array) and uses the exact same O(n) / O(1) negation technique. The two problems are mirrors of each other.

Q4: What if you can only use O(1) extra space and cannot modify the input?

This is First Missing Positive (LC 41) territory and is significantly harder. One approach: binary search on the answer combined with counting. For each candidate mid in [1, n], count how many elements are <= mid. If the count equals mid, then all numbers [1, mid] are present. This is O(n log n) time and O(1) space. The constraint of no modification makes the negation trick impossible — this is exactly how interviewers escalate the difficulty.

Q5: How would you solve this for a very large n where the array doesn't fit in memory?

Stream the array in chunks. In a first streaming pass, write each value into a bitmap (bit k set = number k seen). Then scan the bitmap for unset bits. The bitmap uses O(n/8) bytes — far smaller than storing n integers. For n = 100,000,000, that is about 12 MB versus 400 MB. This is the type of systems-level follow-up that appears in senior engineer interviews.

This Pattern Solves#

The index-as-a-hash-key / in-place negation pattern applies directly to these problems — no new concepts required, just variations on the same insight:

• LeetCode 442 — Find All Duplicates in an Array: same negation pass; collect indices that are already negative when you try to mark them
• LeetCode 287 — Find the Duplicate Number: same domain alignment; use Floyd's cycle detection or binary search instead of negation
• LeetCode 41 — First Missing Positive: same core idea but harder — must place each number at its home index via cyclic sort, then scan for the first mismatch
• LeetCode 645 — Set Mismatch: find the one duplicate and one missing number; combine the duplicate-finding and missing-finding logic from LC 442 and LC 448

All four of these problems appear frequently at Meta, Google, and Amazon. Solving LC 448 correctly — understanding why the domain alignment matters, not just how the negation works — gives you the mental model to handle all of them.

Key Takeaways#

• LeetCode 448 — Find All Numbers Disappeared in an Array is an Easy problem asked at Meta (Facebook) and Amazon; the O(1) space trick is what interviewers expect.
• Key insight: values in [1, n] map naturally to indices [0, n-1], giving a built-in hash function home(v) = v - 1.
• Mark visited indices by negating nums[abs(v) - 1]; any index that stays positive at the end has no corresponding value.
• Two O(n) passes: first negate to mark presence, then collect positive-index positions as the disappeared numbers.
• Time O(n), space O(1) excluding the output list — the negation is done in-place with no auxiliary structure.
• HashSet approach (O(n) space) is the fallback — always mention it, then explain why the negation trick is superior.
• Habit to build: whenever values are bounded by array length, ask if you can encode boolean flags inside the array itself — this unlocks LC 41 (First Missing Positive) and LC 442 (Find All Duplicates).