Java O(n) 1 ms Easy to understand with explanation


  • 0
    A

    Logic: Basically, we are trying to match each number between 1 - n to an index in the array. If we find a number for first time, negate it. If it's a duplicate number, then it will already be negative. That's how we solve 442. Find All Duplicates in an Array. In the end we will be left with some indexes which are having positive value, hence missing.

    Implementation:
    Scan 1: Negate the values at index = nums[i] - 1. We choose nums[i] - 1, since this will ensure we cover each number between 1 - n, and never give us ArrayIndexOutOfBound.
    Scan 2: if a value at index is positive, then index + 1 must be missing!

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

Log in to reply
 

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