# Java O(n) Easy To Understand, Optimal Solution

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

1. All elements in input nums are initially positive
2. 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) {