Index Negation Technique

So I was asked a question find the missing number(s) in an array where the elements are in the range of [1,n] and it(array) contains n integers

Input: [4,3,2,7,8,2,3,1] (n=8, range=[1,8]) 
Output: {5,6}

My first Reaction

My first instinct was to go with a straightforward brute-force solution. But reality hit hard. If I go Brute Force, I will have to pick each number from 1 to n and then search for that number in my input array. That means if my array is too large, it's going to take a lot of operations (O(n^2) time complexity, to be exact). Nobody likes that.

So, I discovered this clever approach called the Index Negation Technique.

THE INDEX NEGATION TECHNIQUE

But before I explain this technique, I want to remind all of you of a very basic concept related to the problem's constraints:

For an array where elements are in the range [1, n], if it were sorted, every element x would be placed at index x-1. For example, the number 1 would be at index 0, the number 2 at index 1, and so on.

This mapping between a value and an index is the foundation of our trick.

Now, here's how the technique works:

You pick an element from the input array. Let's call this value num. You then find the index where num would have been placed if the array was sorted (which is index = abs(num) - 1).

Once that index is found, you negate the value at that specific index to mark it as "seen". You do this for every element in the array.

By doing this, you are using the array itself to keep track of which numbers have been found.

So, why do we need abs()?

That's a great question, and it's the key to making this technique robust. The algorithm would break without using the absolute value (abs()) for two main reasons. Let's use our example: [4,3,2,7,8,2,3,1].

• To handle values at indices that have already been negated.

Imagine our loop is processing the array. We start with the 4, then the 3. When we process the 3 (at index 1), we go to index 2 and negate the value there.

Initial array: [4, 3, 2, 7, ...]
After processing 3: [4, 3, -2, 7, ...]

A moment later, our loop arrives at index 2 to process the element there. The value it reads is no longer 2, but -2.

Without abs(): We would try to calculate the target index for -2, which would be -2 - 1 = -3. This is an invalid index and would crash the program.
With abs(): We take abs(-2), which gives us 2. We then calculate the target index as 2 - 1 = 1. This correctly tells us that the number 2 corresponds to index 1, allowing the algorithm to proceed correctly.

• To correctly process duplicate numbers.

Our example has two 2s and two 3s. Let's see what happens with the two 2s.

When the algorithm first encounters a 2, it goes to index 1 (since 2-1=1) and negates the value there.

Later, when the algorithm encounters the second 2, it needs to do the same thing. It takes abs(2), finds index 1, and sees the value there is already negative. This confirms that a 2 has already been seen, so it simply moves on.

In short, abs() ensures we always use a number's magnitude to find its correct home index. It makes the algorithm work regardless of the order of the elements or whether the values we are reading have already been flipped to negative by a previous step.

Finding the Final Answer

Once you have iterated through the entire input array, you make one final pass. You can just see which values in the array are still positive. A positive value at index i implies that the number i+1 was never present in the original input. These are your missing values!