Find All Numbers Disappeared in an Array: Index Marking

LeetCode Find All Numbers Disappeared in an Array (problem 448) gives you an array of n integers where each value falls between 1 and n. Some elements appear twice, which means some numbers in that range are missing entirely. Your job is to find all the missing numbers in O(n) time and O(1) extra space (not counting the output).

Why this problem matters

This problem is rated easy, but the optimal solution teaches a technique that appears across a whole family of harder array problems. You cannot use a hash set here because the problem asks for O(1) auxiliary space. You cannot sort because that costs O(n log n) time. You need a way to record which numbers are present using only the array itself.

Once you learn the index-marking trick for this problem, you will recognize it immediately in problems like Find All Duplicates, Find the Duplicate Number, and First Missing Positive. It is one of those building blocks that punches well above its weight.

The key insight

Since every value in the array falls between 1 and n, each value maps to a valid index: value v maps to index v - 1. You can use the sign of the element at each index as a one-bit marker. Walk through the array, and for each value, negate the element at the corresponding index. After the pass, any index that still holds a positive value was never visited, which means its corresponding number (index + 1) is missing from the array.

You are using the array itself as a hash map. The keys are the indices. The "values" are the signs of the elements. Negative means "present." Positive means "missing."

The solution

def findDisappearedNumbers(nums):
    for num in nums:
        idx = abs(num) - 1
        if nums[idx] > 0:
            nums[idx] = -nums[idx]

    result = []
    for i in range(len(nums)):
        if nums[i] > 0:
            result.append(i + 1)

    return result

idx = abs(num) - 1 takes the absolute value because earlier iterations may have negated this cell. The original value still matters, and abs() recovers it. Subtracting 1 converts from 1-indexed values to 0-indexed positions.

if nums[idx] > 0 checks whether this index has already been marked. If the element is still positive, no previous value has claimed this spot, so we negate it now. If it is already negative, a previous value already pointed here and we skip it (negating a negative would undo the mark).

Second loop scans the array for any index still holding a positive value. A positive value at index i means no element in the original array had the value i + 1. That number is missing.

Visual walkthrough

Let's trace through nums = [4, 3, 2, 7, 8, 2, 3, 1] step by step. Watch how each value negates its target index, and how the final scan identifies the gaps.

After the marking pass, indices 4 and 5 still hold positive values. That tells us 5 and 6 are missing from the input. Every other number between 1 and 8 appeared at least once.

Complexity analysis

Time: Two passes through the array. The first marks indices, the second collects results. Each pass is O(n), so the total is O(n).

Space: The output list is required by the problem and does not count. The only extra variables are idx, num, i, and result. That is O(1) auxiliary space.

Edge cases

No missing numbers: nums = [1, 2, 3, 4]. Every index gets negated. The second loop finds no positive values. Result: [].

All same value: nums = [1, 1, 1, 1]. Only index 0 gets negated. Indices 1, 2, and 3 stay positive. Result: [2, 3, 4].

Single element: nums = [1]. Index 0 gets negated. No positives remain. Result: [].

Maximum missing: nums = [1, 1, 1, 1, 1]. Only index 0 is negated. Indices 1 through 4 stay positive. Result: [2, 3, 4, 5].

Already in order: nums = [1, 2, 3, 4, 5]. Every value marks its own index. All indices go negative. Result: [].

The building blocks

Index as hash map

When array values are bounded by the array length, you can treat each value as a key that maps to an index. Instead of allocating a separate data structure, you encode information directly in the array. The constraint 1 <= a[i] <= n guarantees that a[i] - 1 is always a valid index, so no bounds checking is needed.

This micro-pattern shows up in:

• Find All Duplicates in an Array (LeetCode 442) where a second negation attempt reveals duplicates.
• First Missing Positive (LeetCode 41) where cyclic sort places values at their "home" index.
• Missing Number (LeetCode 268) where index summation or XOR identifies the absent value.

In-place sign marking

The sign of each element acts as a boolean flag. Negative means "the value corresponding to this index has been seen." Positive means "not yet seen." This lets you track membership across the full range of values without any extra memory. The key detail is always taking abs() before using a cell's value, because the sign carries marking information, not the original data.

From understanding to recall

The algorithm is two short loops. The first negates, the second collects. But when you sit down in an interview and the screen is blank, you need the mapping value -> index = abs(value) - 1 to be automatic. You also need to remember the guard: only negate if the target is still positive.

Write the solution from scratch. Do it again in two days. Then again next week. After a few reps, the pattern stops being something you reconstruct and starts being something you just know. That is the difference between understanding a solution and being able to produce it under pressure.

Related posts

• Find the Duplicate Number - Same value-to-index mapping, but uses Floyd's cycle detection to find the single duplicate in O(1) space.
• Find All Duplicates in an Array - The mirror image of this problem. Instead of collecting indices that stay positive (missing), you collect values whose target index is already negative (duplicates).
• First Missing Positive - The hard variant. Values are not bounded by n, so you need cyclic sort instead of sign negation.