Smallest Positive Missing Number in an Unsorted Array in C++

Problem :

We have an array consisting of negative and positive numbers, we have to finding the smallest missing positive number from the given array.

Let’s understand it better with an example: [-1, 2, 1, -2, 7, 4] the smallest positive missing number is 3 ( as we have 1, 2, 4, 7 from the positive ones).

If you’re here then that means none of the other solutions have worked for you or maybe they were too difficult for you to understand. Trust me, at first it was difficult for me too until I came across this solution, which is going to make you say ‘woah’. Here we go!

Solution :

Somethings to keep in mind:

1. Ignore the negative numbers, i.e. less than 0.
2. The numbers greater than N (we’ll see why)

Considering the above example, this is what we have:

Our aim is to, swap the numbers in the array in such a way that it ‘maps’ with the index value. Like for the index value 1, we have -1, for the index value 2, we have 2 (and that’s what we wanted to achieve. Its a total coincidence lol) and so on.

Now, we will check the array for positive values which is greater than 1 (not considering 0) and for the values less than N, as we need to maintain the max array size of N since we are ‘mapping’ the values with its index. We will consider only the positive array values, so the resulting array we have is:

I have marked the last value as pink because its on its correct index value. The same thing we want to achieve.

Steps

1. Traverse through the entire array.
2. Consider only the numbers that are positive (≤1), less than N (≤n) and are don’t have the value same as its index value (arr[i] != arr[arr[i]-1]), which in our case is 4.
3. If you get such numbers, swap them.
4. Again traverse the array. Now, you will see the number which isn’t on it’s corresponding index value is our smallest missing positive number.

This is what we have with us:

The value 1 is at index 1, 2 is at index 2, 4 was already on index 4. The only remaining index is 3 that doesn’t have 3 instead it contains 7.

5. We return the index value 3. Easy peasy!

If you are not a beginner, then I would suggest you don’t read any further. All you need is the understanding of the solution and not the solution itself.

If you are unable to figure out the code, here it is:

Code

Hope you got your head clear now.

Happy Coding !