Excuse me, that’s MY SPOT!

Every Jack has his Jill.
Every man can expect to have his partner.

Recently, I did some interesting array-related interview questions. The problem description starts like this or similar: Given an array nums containing n numbers in the range [0, n] … and asks you to find duplicate/missing numbers.

Here is one of the problem description

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.
For example,
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]

The SO-EASY Solution

One can quickly come up with a solution which uses an additional array to store each of the element at its correct spot.

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        int[] temp = new int[n];
        for (var num : nums) {
            temp[num - 1] = num;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (temp[i] == 0) {
                res.add(i + 1);
            }
        }
        return res;
    }
}

That’s it! Thanks for reading ;) I’m kidding. This might be the appetizer or warm-up for the interview and your interviewer can ask you to improve the space or time complexity.

The Impress Me Solution

One can be asked to improve the space complexity by not using the extra array. Is that achievable? Of course. Recall what is the purpose of the extra array? It’s a temporary place to put each element at its correct spot.

Since each element’s value is within the array’s index, I can actually try to put them in the correct spot by swapping elements of the original array. Here is the illustration.

Swap elements to the correct spot. The red block is the current element; the green one indicated the expected spot; the blue ones are elements in the correct spots; the grey ones are extra.

Like the old saying goes: Every Jack has his Jill. We’ve put almost every element in the correct spot except for the extra 2 and 3 in the grey blocks. That’s what the original ask of the interview question. After the swapping, we can…