Domain 1EasyCORE

Find All Numbers Disappeared in an Array

The problem requires us to identify all integers in the range `[1, n]` that do not appear in the given array `nums`. The input is an array of integers where each integer is within the range `[1, n]`, and the length of the array is also `n`. The output should be a list of missing integers.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

448. Find All Numbers Disappeared in an Array

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 56.1%


Problem Breakdown

The problem requires us to identify all integers in the range [1, n] that do not appear in the given array nums. The input is an array of integers where each integer is within the range [1, n], and the length of the array is also n. The output should be a list of missing integers.

Inputs:

  • An array nums of integers where 1 <= nums[i] <= n.

Outputs:

  • A list of integers that are in the range [1, n] but do not appear in nums.

Implicit Constraints:

  • The length of nums is exactly n.
  • Each integer in nums is within the valid range [1, n].
  • The returned list should not count as extra space for complexity calculations.

Tricky Edge Cases:

  • An empty array (though the problem constraints prevent this).
  • Arrays with all elements being the same.
  • Arrays where all numbers from 1 to n are present.

Intuition

A brute-force approach would involve creating a set of all integers from 1 to n and then removing each integer found in nums. The remaining integers in the set would be the missing numbers. However, this approach requires extra space for the set and has a time complexity of O(n).

The key insight is to use the input array itself to track which numbers have been seen by marking their corresponding indices. This way, we can achieve the desired solution without using extra space.

Approach

  1. Iterate through the array: For each number nums[i], treat it as an index (subtract 1 to adjust for zero-based indexing) and mark the value at that index as negative if it’s positive.
  2. Identify missing numbers: After marking, any index with a positive value indicates that the corresponding number is missing from the array.

Algorithm:

  • Iterate through each element in nums.
    • For each element nums[i], find the index idx = abs(nums[i]) - 1.
    • If nums[idx] is positive, mark it as negative by setting nums[idx] = -nums[idx].
  • After marking, iterate again to collect all indices with positive values. These indices correspond to missing numbers.

Complexity Analysis

Time Complexity: O(n)

  • We make two passes through the array: one for marking and another for collecting results. Each pass is O(n).

Space Complexity: O(1) (excluding the output list)

  • We modify the input array in place without using any additional data structures, thus achieving constant space complexity.

Solution

def findDisappearedNumbers(nums):
    # Mark each number's corresponding index as negative
    for num in nums:
        idx = abs(num) - 1
        if nums[idx] > 0:
            nums[idx] = -nums[idx]
    
    # Collect all indices with positive values, which are missing numbers
    result = []
    for i in range(len(nums)):
        if nums[i] > 0:
            result.append(i + 1)
    
    return result

Edge Cases Handled

  • All elements are the same: If all elements are the same, the marking step will only affect one index, and the rest will remain positive, correctly identifying missing numbers.
  • No duplicates: The algorithm naturally handles arrays with no duplicates by marking indices accordingly.
  • All numbers from 1 to n present: In this case, all indices will be marked negative, resulting in an empty output list as expected.