Find all numbers disappeared in an array

Back to index

From the LeetCode problem with the same name. The problem statement is:

Given an array of integers where 1<=a[i]<=n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1,n] inclusive that do not appear in this array.

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

If we can use extra space the problem is easy: we use a Set to keep track of the remaining elements.

If we want to do the question in-place we should use the fact that there is a natural choice of where to store each element. Namely at the key that it corresponds to. I.e. we can store 4 in the 3rd position (0-indexed). Then the only problem is to avoid overwriting elements.

To avoid overwriting elements we proceed in a chain. Whenever we move an element to the position corresponding to its value we immediately consider the element we just displaced and move it next. There is no guarantee that the whole array will be finished in one chain. Therefore we have to keep track of our starting point and start another chain if we need to.

A full solution could be as follows:

class Solution {
  public List<Integer> findDisappearedNumbers(int[] nums) {
    moveValuesToTheirKey(nums);

    List<Integer> missing = new LinkedList<Integer>();
    for (int j = 0; j < nums.length; j++) {
      if (nums[j] == 0) missing.add(j + 1);
    }    

    return missing;
  }

  void moveValuesToTheirKey(int[] nums) {
    int i = 0;
    while (i < nums.length) {
      int value = nums[i];
      if (value - 1 == i) {
        i++;
        continue;
      }

      nums[i] = 0;
      while (0 < value && value <= nums.length) {
        value = swapIn(value, nums);
      }
      i++;
    }
  }

  int swapIn(int value, int[] nums) {
    int target = nums[value - 1];
    if (value == target) return -1;
    nums[value - 1] = value;
    return target;
  }
}

Having looked through some other submissions on LeetCode I learnt another trick. Instead of moving the values one can come up with a way of marking which positions have been used. The most common way to do this was by replacing the target position with its negation. In a way this solution uses more memory because now the integers must be signed.