# Java O(n) inspace solution with explanation

• Iterate and visit every element in the given array. For each iteration, we travel from `a[i]` to `a[a[i]-1]` and continue doing so until we reach a position that we visited in advance. we assign 0 to `a[i]` whenever we visit it. After this iteration, we iterate the whole array again and if an element `a[i] != 0`, i+1 would be one missing number.
For example: [2,3,2,1],
In the first iteration, a[0] = 2 -> we move to a[2-1] and mark a[1] = 0. Because a[1] = 3 -> we move to a[3-1] = 2. And mark a[2] = 0. Now we move to a[1] and a[1] = 0, we stop this iteration. We check a[1], a[2] == 0, so we do nothing in those two iterations. But a[3] = 1 -> we move to a[0] and let it to 0. Finally, we get [0,0,0,1].
In the checking step, we find only a[3] != 0, so we miss value of 4 in this array.

``````public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> output = new ArrayList<Integer>();
for(int i = 0; i < nums.length; i++){
if(nums[i] != 0){
int j = nums[i]-1;
while(nums[j]!=0){
int hold = nums[j]-1;
nums[j] = 0;
j = hold;
}
}
}
for(int i = 0; i < nums.length; i++){
if(nums[i] != 0)
}
return output;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.