Find All Numbers Disappeared in an Array

author: Sergei Golitsyn

more problems here: https://t.me/crack_code_interview

problem link: https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

Description:

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]

Solution:

Ok, based on a description we know, we have an array from 1 to n.

And if we have for example array [2,1] we can try to swap elements.

I mean, if on a 0 position we have 1 that is correct. Otherwise, let’s swap elements. And we can swap it when an element doesn’t equal position.

We have an array [1,2,1] → reader equals 2. We check if condition

nums[reader] = nums[2] = 1

nums[nums[reader] — 1] = nums[1–1] = nums[0] = 1 → that is the main idea of this algorithm.

If we already have an element on the correct position we skip it.

And then, we should check elements on their positions. Because we know that we have an array from 1 to n, we can add an invalid element index to the result.

Let’s code it.

public List<Integer> findDisappearedNumbers(int[] nums) {
   List<Integer> rez = new ArrayList<>();
   int reader = 0;
   while (reader < nums.length) {
      if (nums[reader] != nums[nums[reader] - 1]) {
         swap(nums, reader, nums[reader] - 1);
      } else {
         reader++;
      }
   }
   for (int i = 0; i < nums.length; i++) {
            if (i != nums[i] - 1) {
                rez.add(i + 1);
            }
        }
        return rez;
}
    
private static void swap(int[] nums, int a, int b) {
   int tmp = nums[a];
   nums[a] = nums[b];
   nums[b] = tmp;
}

I want to repeat it here again. The main trick is

if (nums[reader] != nums[nums[reader] - 1])

nums[reader] — current element.

nums[nums[reader] — 1] — element in array with index == element on nums[reader] position.

Enjoy and have fun!