Find the first missing positive entry 22.2 slightly more efficient solution

#1

Hi All!

I might have a slightly more efficient solution for 22.2 than what is presented.
Please check my logic if it is missing something.

static int firstMissingPositiveEntry(int[] arr) {
    int N = arr.length;
    for (int i = 0; i < N; ) {
        if (arr[i] < 1 || arr[i] > N) {
            arr[i] = arr[--N];
            continue;
        } else if (!swap(arr, arr[i]-1, i)){
          ++i;
        }
    }

    int i = 0;
    for(; i < N && arr[i]-1 == i; ++i);

    return i+1;
}

static boolean swap(int[] arr, int i, int j) {
    if (arr[i] == arr[j]) return false;
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    return true;
}
0 Likes
#2

Hey madno,

Would you mind to explain how this algorithm works and why it is more efficient? Assuming you are at an interview, you need to explain why this algorithm works. I already have my own understanding to this but it would be nice to see how you approach this problem.

0 Likes
#3

Thanks for putting the time into checking out my take on this problem.

TL,DR:
As the first loop processes the input array, the search range where the
first missing positive entry (FMPE) is located might be tightened.
Because of the tightening and rearranging of the array, the first loop
can stop earlier than the end of the initial array.
This is where the slight improvement is coming from (not considering
caching architecture :slight_smile: ).

A more detailed explanation:
Initially we have N numbers in the array and the FMPE is a number somewhere between
[1…N+1], bounds included. For simplicity, let’s suppose that initially we expect, that the array will hold
all the numbers [1…N] in some random order. The first loop will bucket sort the values.
and the second loop will check the buckets and report N+1 as the FMPE.

If the bucket sort finds an outlier, an outlier is a value from the array
which is outside of the range [1…N], we have to change our expectation
given this new information. From now on we will think about the array as
at most N-1 different values between [1…N] and at least one outlier. There
is at least one value missing from the range [1…N], whose spot is occupied
by the outlier. This missing value or some smaller one will be our FMPE.
Now we can define a new array, by throwing away the outlier, overwriting
it with the value at the end of the array. The array could be shrunk,
instead of some expensive shrinking, it is enough to store the remaining length
of the array.
Now we transformed the initial problem into an equivalent one, where the input
array is smaller.

The variant of the first loop, guaranteeing it’s termination:

  • current value is an outlier, value at the end of the array overwrites current value, array is shrunk by one
  • array value at cursor is in the search range, cursor array value is copied to its respective bucket, the value inside the bucket is copied to the cursor location. If these two values match, we don’t have a variant. In this case we have to move the cursor.
  • to prove that the variant holds, we also need to prove, that there are no swap loops. This is true because once a value is moved to it’s bucket, it won’t be changed in the actual swap loop again.
0 Likes