Code Implementation

class Solution:
    def findDisappearedNumbers(self, nums):
        for i in range(len(nums)):
            index = abs(nums[i]) - 1
            if nums[index] > 0:
                nums[index] = -nums[index]
        return [i + 1 for i in range(len(nums)) if nums[i] > 0]
      

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            int index = abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        vector<int> result;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) result.push_back(i + 1);
        }
        return result;
    }
};
      

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) result.add(i + 1);
        }
        return result;
    }
}
      

var findDisappearedNumbers = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        let index = Math.abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }
    let result = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) result.push(i + 1);
    }
    return result;
};
      

Problem Description

You are given an array of integers nums where nums has length n and contains numbers between 1 and n (inclusive). Some numbers may appear more than once, while others may be missing. Your task is to find all numbers in the range 1 to n that do not appear in nums, and return them as a list.

• Each number in nums is between 1 and n (inclusive).
• You must find all numbers in this range that are missing from the array.
• You should not use extra space for another array (O(1) extra space, not counting the output).
• The solution should run in O(n) time.

Thought Process

At first glance, the problem seems to ask for a simple search: for each number from 1 to n, check if it's in nums. A brute-force approach would use nested loops, checking every number for existence, but this would be inefficient (O(n^2)). A better idea is to use a set or hash map to record which numbers are present, then output those missing. However, the problem restricts us from using extra space (besides the output), so we need to be clever.

The key insight is that since all numbers are in the range 1 to n, we can use the input array itself to store information about which numbers we've seen, by marking elements in a way that doesn't require extra space. This leads us to an in-place marking strategy.

Solution Approach

• Step 1: Marking Presence
  • Iterate through each element num in nums.
  • For each num, compute its corresponding index: index = abs(num) - 1.
  • Mark the element at nums[index] as negative to indicate that the number index + 1 exists in the array.
  • If the element is already negative, leave it (we only care that it has been seen).
• Step 2: Collect Missing Numbers
  • After marking, iterate through nums again.
  • For each index i, if nums[i] is positive, it means the number i + 1 was never seen in the array.
  • Add i + 1 to the result list.
• Why This Works
  • We only use the sign of elements in nums to mark presence, so we do not need extra space.
  • All indices correspond naturally to the numbers 1 to n.
  • The time complexity is O(n) as we only traverse the array a constant number of times.

Example Walkthrough

Suppose nums = [4,3,2,7,8,2,3,1].

1. Marking Step:
   • i=0, num=4: Mark nums[3] (was 7) as negative → nums becomes [4,3,2,-7,8,2,3,1]
   • i=1, num=3: Mark nums[2] (was 2) as negative → nums becomes [4,3,-2,-7,8,2,3,1]
   • i=2, num=-2: Mark nums[1] (was 3) as negative → nums becomes [4,-3,-2,-7,8,2,3,1]
   • i=3, num=-7: Mark nums[6] (was 3) as negative → nums becomes [4,-3,-2,-7,8,2,-3,1]
   • i=4, num=8: Mark nums[7] (was 1) as negative → nums becomes [4,-3,-2,-7,8,2,-3,-1]
   • i=5, num=2: nums[1] already negative, skip
   • i=6, num=-3: nums[2] already negative, skip
   • i=7, num=-1: nums[0] (was 4) as negative → nums becomes [-4,-3,-2,-7,8,2,-3,-1]
2. Collecting Missing Numbers:
   • nums[0] = -4 (negative) → 1 is present
   • nums[1] = -3 (negative) → 2 is present
   • nums[2] = -2 (negative) → 3 is present
   • nums[3] = -7 (negative) → 4 is present
   • nums[4] = 8 (positive) → 5 is missing
   • nums[5] = 2 (positive) → 6 is missing
   • nums[6] = -3 (negative) → 7 is present
   • nums[7] = -1 (negative) → 8 is present
3. Result:
   • The missing numbers are [5, 6].

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O(n^2), since for each number from 1 to n, we may need to scan the entire array.
  • Space Complexity: O(1), but very slow for large arrays.
• Hash Set Approach:
  • Time Complexity: O(n), as we scan the array and build a set.
  • Space Complexity: O(n), since we need to store up to n elements in a set.
• Optimized (In-place Marking) Approach:
  • Time Complexity: O(n), as we traverse the array a constant number of times.
  • Space Complexity: O(1), since all marking is done in the input array itself and only the output list is extra.

Summary

This problem demonstrates a clever use of in-place array manipulation to record which numbers are present without using extra space. By leveraging the properties of the input (numbers from 1 to n), we can mark seen numbers by negating their corresponding indices. This approach is both efficient and elegant, achieving O(n) time and O(1) extra space. The main insight is recognizing that the input array itself can be used as a data structure to store auxiliary information, avoiding the need for additional memory.