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.

The solution uses the input array itself to track the presence of numbers without requiring additional memory. Since all values are in the range [1, n], each number can be mapped to an index in the array.

For every number encountered, the element at the corresponding index is marked as visited by converting it to a negative value. After processing the entire array, any index containing a positive value indicates that its corresponding number was missing from the original array.

This approach is efficient because it avoids using extra data structures such as HashSet or HashMap.

Java Solution:

import java.util.ArrayList;
import java.util.List;

public class FindDisappearedNumbers {

    public static List<Integer> findDisappearedNumbers(int[] nums) {

        List<Integer> missingNumbers = new ArrayList<>();

        for (int index = 0; index < nums.length; index++) {
            int mappedIndex = Math.abs(nums[index]) - 1;

            if (nums[mappedIndex] > 0) {
                nums[mappedIndex] = -nums[mappedIndex];
            }
        }

        for (int index = 0; index < nums.length; index++) {
            if (nums[index] > 0) {
                missingNumbers.add(index + 1);
            }
        }

        return missingNumbers;
    }

    public static void main(String[] args) {

        int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};

        List<Integer> result = findDisappearedNumbers(nums);

        System.out.println(result);
    }
}

Output: [5, 6]

Time Complexity: O(n), where n is the size of the array. The array is traversed twice, resulting in linear time complexity.

Space Complexity: O(1) auxiliary space, as the algorithm modifies the input array itself. The output list is not considered extra space in complexity analysis.

Key Interview Points: • The constraint nums[i] ∈ [1, n] enables index-based marking techniques. • Negating values is a common in-place strategy for tracking visited elements. • A HashSet-based solution is simpler to understand but requires O(n) additional space. • This problem frequently appears in interviews to test in-place array manipulation techniques.