Java O(n) inspace solution with explanation


  • 0
    T

    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)
                    output.add(i+1);
            }
            return output;
        }
    }
    

Log in to reply
 

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