448. Find All Numbers Disappeared in an Array(Solution || Leetcode easy || Java)

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

Input: nums = [1,1]
Output: [2]

Constraints:

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

SOLUTION:

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        //As given to us numbers are in the range of 1 to n,
       // hence, by this we understand that we are going to
       // use cyclic sort
        
        int i = 0;
        
        while(i < nums.length){
            int correct = nums[i] - 1;
            
            if(nums[i] != nums[correct]){
                int temp = nums[i];
                nums[i] = nums[correct];
                nums[correct] = temp;
            }else{
                i++;
            }
        }
        
        List<Integer> ans = new ArrayList<>();
        
        for(int j = 0; j < nums.length; j++){
            if(nums[j] != j+1){
                ans.add(j+1);
            }
        }
        
        return ans;
    }
}

Runtime: 8 ms, faster than 83.75% of Java online submissions for Find All Numbers Disappeared in an Array.

Memory Usage: 67.4 MB, less than 41.40% of Java online submissions for Find All Numbers Disappeared in an Array.

Thank you for reading. If you have any queries then, please let me know in the comment section. I will surely be responsive toward it.