0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You should copy relevant part because links tend to rot. Besides, it is far better to narrow down question, to exclude parts that you do understand. $\endgroup$ – Evil Jun 23 '18 at 23:57
1
$\begingroup$

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]$.

$\endgroup$
  • 1
    $\begingroup$ Thanks alot that's much clearer now. for your question If all elements of B are true, then n+1 is the smallest positive integer not present (why?) Now If all the elements are true this mean that all numbers are presented sequentially for 1 to n then the minimum missing one is n+1. $\endgroup$ – Samar Jun 26 '18 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.