448. Find All Numbers Disappeared in an Array

Posted on | Edited on | Views:

LeetCode

Approach 1: O(n) Space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> ls=new ArrayList<>();
        
        int[] counter=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            counter[nums[i]-1]++;
        }
        for(int i=0;i<nums.length;i++){
            if(counter[i]==0) ls.add(i+1);
        }
        
        return ls;
    }
}

link
Approach 2: O(1) Space InPlace Modification Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> ls=new ArrayList<>();
        
        for(int i=0;i<nums.length;i++){
            int idx=Math.abs(nums[i])-1;
            if(nums[idx]>0){
                nums[idx]=-nums[idx];
            }
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0) ls.add(i+1);
        }
        
        return ls;
    }
}

0%