Finding the smallest positive missing number in array of integers contains negative and duplicates number

Question

I found this solution but I don't understand it. Can anyone explain the idea behind it ?

the solution:

A O(n) time and O(1) extra space solution:
The idea is similar to this post. We use array elements as index. To mark presence of an element x, we change the value at the index x to negative. But this approach doesn’t work if there are non-positive (-ve and 0) numbers. So we segregate positive from negative numbers as first step and then apply the approach.

Following is the two step algorithm.

1. Segregate positive numbers from others i.e., move all non-positive numbers to left side. In the following code, segregate() function does this part.

2. Now we can ignore non-positive elements and consider only the part of array which contains all positive elements. We traverse the array containing all positive numbers and to mark presence of an element x, we change the sign of value at index x to negative. We traverse the array again and print the first index which has positive value.

Answer 1

The solution has two parts. The first part filters out all non-positive numbers - this can be done in-place using the partition subroutine of quicksort.

After the first part, we have an array $A[1],\ldots,A[n]$ of positive numbers, and we want to find the smallest positive integer which is not present. We create a new Boolean array $B[1],\ldots,B[n]$ initialized to false. We go over all elements in $A$, and whenever we find an element $i \leq n$, we set $B[i]$ to true. We then find the smallest index $i$ such that $B[i]$ is false - this is the smallest positive integer which is not present. If all elements of $B$ are true, then $n+1$ is the smallest positive integer not present (why?).

As an optimization, we store the array $B$ by modulating the sign of elements in $A$: to represent $B[i]$ being false we use a positive sign for $A[i]$, and to represent $B[i]$ being true we use a negative sign for $A[i]$.