Find All Numbers Disappeared in an Array

Problem

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

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

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

Solution

Time complexity O(n)

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

Analysis

The problem defines that all elements in given array will in the range of 1 to n inclusively
Therefore, to get the index we need to subtract one on the absolute value of array
We mark the index we get from the value of array as its negative value
Then we loop through the array again, and add i+1 as disappeared number in our res
The key to do this problem without extra space is that we optimize the value of array as index
Then apply that index into the array again and mark using negative values