**Explanation**

The idea to this problem is to take advantage of two important facts:

- All elements in input
*nums*are initially**positive** - All elements are
**within range [1, n]**, where n is the length of*nums*.

So, for any element, *x*, in *nums*, we know that by fact 2), *nums[x-1]* exists.

To mark which elements exist in *nums* for later use, we apply fact 1): if we encounter an element of value *x* and *nums[x-1]* > 0, by setting *nums[x-1]* = -*nums[x-1]*, this informs us that element x exists within *nums*, **BUT** we may encounter **negative** indices from now on, so we must use **absolute** values to encounter only positive indices.

```
// Example:
//int [] nums = { 5, 5, 5, 5, 5 }
// Suppose we're considering index 0 first. Since the absolute value of
// nums[0] equals 5 and nums[5-1] > 0, we set nums[5-1] = -nums[5-1].
// Our array now is { 5, 5, 5, 5, -5 }; this means 5 has been found.
// nums = { 5, 5, 5, 5, -5 }
// Suppose we're now considering index 4. Since the absolute value of
// nums[4] equals 5 and nums[5-1] < 0, 5 has been found already, so we
// don't need to set nums[5-1] = -nums[5-1].
```

Lastly, we iterate through all elements. If we encounter an element, nums[i], where nums[i] > 0, then that means element i+1 was never encountered in *nums*.

If you're confused about the x-1, i+1 logic, remember that the indices in *nums* span from 0...n-1 while the numbers we are tracking span from 1...n.

**Time Complexity**

The time complexity is O(n) where n is the number of elements in *nums*, since we iterate through *nums* twice - the first time to mark elements, the second time to generate our *result*.

```
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int num : nums) {
int absNum = Math.abs(num);
// We mark nums by setting the element at index absNum-1
// as negative; this later tells us absNum exists
if (nums[absNum - 1] >= 0) {
nums[absNum - 1] = -nums[absNum - 1];
}
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
// If the number is positive, it means value (i+1) not found
if (nums[i] > 0) {
result.add(i + 1);
}
}
return result;
}
}
```