# Find All Numbers Disappeared in an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/find-all-numbers-disappeared-in-an-array
**Data structures:** Array, Hash Table
**Companies:** [Tinkoff](https://scaleengineer.com/companies/tinkoff)
---
## Problem
Given an array `nums` of `n` integers where `nums[i]` is in the range `[1, n]`, return _an array of all the integers in the range_ `[1, n]` _that do not appear in_ `nums`.

**Example 1:**

**Input:** nums = [4,3,2,7,8,2,3,1]
**Output:** [5,6]

**Example 2:**

**Input:** nums = [1,1]
**Output:** [2]

**Constraints:**

* `n == nums.length`
* `1 <= n <= 105`
* `1 <= nums[i] <= n`

**Follow up:** Could you do it without extra space and in `O(n)` runtime? You may assume the returned list does not count as extra space.

# Approaches
## Brute Force Iteration
This is the most straightforward approach. We iterate through all the numbers from 1 to `n`. For each number, we perform another iteration through the input array `nums` to check if the number exists. If it doesn't, we add it to our list of disappeared numbers.
**Time:** O(n^2), where `n` is the number of elements in the array. For each of the `n` numbers from 1 to `n`, we might scan the entire array of `n` elements. · **Space:** O(1) extra space. The space used by the result list is not considered extra space as per the problem description.
**Pros:** Simple to understand and implement.; Does not modify the input array.; Uses constant extra space (excluding the result list).
**Cons:** Very inefficient, with a quadratic time complexity.; Will result in a 'Time Limit Exceeded' error on most platforms for larger inputs.
### Explanation
The algorithm works by checking every number in the range `[1, n]` for its presence in the input array `nums`.
- We loop from `i = 1` to `n`.
- In each iteration, we have a flag, say `found`, initialized to `false`.
- We then start a nested loop to traverse the `nums` array.
- If we find an element in `nums` that is equal to `i`, we set `found` to `true` and break the inner loop, as we only need to know if it exists at least once.
- After the inner loop completes, if the `found` flag is still `false`, it means `i` was not present in `nums`, so we add it to our result list.
- This process is repeated for all numbers from 1 to `n`.
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 1; i <= n; i++) {
            boolean found = false;
            for (int num : nums) {
                if (num == i) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                result.add(i);
            }
        }
        return result;
    }
}
```
### Algorithm
- 1. Initialize an empty list `result` to store the disappeared numbers.
- 2. Get the size of the array, `n`.
- 3. Loop through each integer `i` from 1 to `n`.
- 4. For each `i`, search for its presence in the `nums` array by iterating through `nums`.
- 5. If `i` is not found in `nums` after checking all its elements, add `i` to the `result` list.
- 6. After the outer loop finishes, return the `result` list.

## Using a Hash Set
A more optimized approach involves using a data structure that provides fast lookups, such as a hash set. We can first iterate through the input array and store all its elements in a hash set. Then, we iterate from 1 to `n`, and for each number, we check if it's in the hash set. If it's not, we add it to the result list.
**Time:** O(n). It takes O(n) to build the hash set and another O(n) to iterate from 1 to `n`. · **Space:** O(n). In the worst case, all numbers in `nums` are unique, and the hash set will store `n` elements.
**Pros:** Much faster than the brute-force approach, with a linear time complexity.; Relatively easy to understand.; Does not modify the input array.
**Cons:** Requires extra space proportional to the number of elements in the array, which does not meet the follow-up constraint of O(1) space.
### Explanation
This method improves the time complexity by sacrificing space. The core idea is to trade space for time by using a hash set to record which numbers are present in the input array.
- First, create a `HashSet` and populate it with all the numbers from the `nums` array. This takes O(n) time.
- Then, create an empty list for the results.
- Loop from `i = 1` to `n`. For each `i`, check if it exists in the hash set. Checking for an element in a hash set takes, on average, O(1) time.
- If `i` is not in the set, it means it's a disappeared number, so add it to the result list.
- This second loop also takes O(n) time.
- The total time complexity is therefore linear.
```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            seen.add(num);
        }

        List<Integer> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 1; i <= n; i++) {
            if (!seen.contains(i)) {
                result.add(i);
            }
        }
        return result;
    }
}
```
### Algorithm
- 1. Create a `HashSet` named `seen`.
- 2. Iterate through each number `num` in the input array `nums` and add it to the `seen` set.
- 3. Initialize an empty list `result`.
- 4. Get the size of the array, `n`.
- 5. Loop through each integer `i` from 1 to `n`.
- 6. Check if `i` is present in the `seen` set. This is an O(1) average time operation.
- 7. If `i` is not in the set, add it to the `result` list.
- 8. Return the `result` list.

## In-place Marking using Negation
This is the most optimal approach, satisfying the follow-up constraint of O(1) extra space. The key insight is that the numbers are in the range `[1, n]`, which corresponds to the valid indices `[0, n-1]` of the array. We can use the array itself to mark the presence of numbers. We iterate through the array, and for each number `x`, we go to the index `x-1` and mark it (e.g., by negating the value at that index). A second pass over the array allows us to find which indices were not marked, corresponding to the missing numbers.
**Time:** O(n). We perform two separate passes through the array, each taking O(n) time. O(n) + O(n) = O(n). · **Space:** O(1) extra space. The modification is done in-place, and the space for the result list is excluded.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1) (as the result list is not counted).; Meets the follow-up constraints.
**Cons:** Modifies the input array. If the caller needs the original array to be preserved, a copy must be made first, which would use O(n) space.
### Explanation
This clever approach utilizes the input array itself as a hash map to keep track of the numbers we've seen, thus achieving O(1) space complexity.
- The values in the array range from `1` to `n`. This means we can map each value `x` to an index `x - 1`.
- We iterate through the `nums` array once. For each number `nums[i]`, we find the corresponding index `index = Math.abs(nums[i]) - 1`. We use the absolute value because the element at `nums[i]` might have been negated in a previous step.
- At this `index`, we mark the element `nums[index]` as seen by making it negative. If it's already negative, we leave it as is. This ensures that even if a number appears multiple times, its corresponding index is marked only once.
- After this first pass, the array is modified. For any number `k` from `1` to `n` that was present in the original array, the element at index `k-1` will now be negative.
- We then perform a second pass through the modified array from index `i = 0` to `n-1`.
- If we find that `nums[i]` is positive, it means the number `i + 1` was never seen in the original input. We add `i + 1` to our result list.
- Finally, we return the result list.
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // First pass: Mark seen numbers by negating the value at the corresponding index.
        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<>();
        // Second pass: Find the positive numbers, which correspond to missing integers.
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                result.add(i + 1);
            }
        }

        return result;
    }
}
```
### Algorithm
- 1. Iterate through the `nums` array. For each element `num`:
- 2. Calculate the target index: `index = Math.abs(num) - 1`.
- 3. If the value at `nums[index]` is positive, multiply it by -1 to mark it as seen.
- 4. After the first loop, initialize an empty list `result`.
- 5. Iterate through the `nums` array from `i = 0` to `n-1`.
- 6. If `nums[i]` is positive, it means the number `i + 1` was never in the original array. Add `i + 1` to `result`.
- 7. Return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> findDisappearedNumbers(int[] nums) {
    int n = nums.length;
    for (int x : nums) {
      int i = Math.abs(x) - 1;
      if (nums[i] > 0) {
        nums[i] *= -1;
      }
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      if (nums[i] > 0) {
        ans.add(i + 1);
      }
    }
    return ans;
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]: for x in nums: i = abs(x) - 1 if nums[i] > 0: nums[i] *= - 1 return [i + 1 for i in range(len(nums)) if nums[i] > 0]

```