# Speed up searching for the lowest element that is not in the array

I try to solve this question: B. Informatics in MAC at Codeforces To solve it, I think I need to calculate the prefix and suffix array of MEX. I made observation that making only 1 subsegment will give good answer. We are required to make at least 2, but we know that MEX of every segment must be equal, so making segments as large as possible is optimal.

Due to this, we just can calculate prefix and suffix arrays of MEX, and if at some index i they are equal, we have the answer.

The problem is: how to calculate it efficiently? That my current code:

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

int t;
cin >> t;

while (t--) {
int n;
cin >> n;

vector<int> a(n);
int a_max = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
a_max = max(a_max, a[i]);
}

vector<int> mex_prefix(n);
vector<int> mex_suffix(n);
mex_prefix[0] = a[0] > 0 ? 0 : 1;
mex_suffix[n - 1] = a[n - 1] > 0 ? 0 : 1;

// Problematic part starts here
set<int> s1{ a[0] };
set<int> s2{ a[n - 1] };
for (int i = 1, j = n - 2; i < n && j >= 0; ++i, --j) {
s1.insert(a[i]);
s2.insert(a[j]);

for (int val = 0; val <= a_max + 1; ++val) {
if (s1.find(val) == s1.end()) {
mex_prefix[i] = max(mex_prefix[i - 1], val);
break;
}
}

for (int val = 0; val <= a_max + 1; ++val) {
if (s2.find(val) == s2.end()) {
mex_suffix[j] = max(mex_suffix[j + 1], val);
break;
}
}
}
// End

bool valid = false;
int i = 0;
for (; i < n - 1; ++i) {
if (mex_prefix[i] == mex_suffix[i + 1]) {
valid = true;
break;
}
}

if (!valid) {
cout << -1 << '\n';
}
else {
cout << 2 << '\n';
cout << 1 << ' ' << i + 1 << '\n';
cout << i + 2 << ' ' << n << '\n';
}
}
}


I will discuss it for prefix array, because building suffix array is analogous.

We set 0-th index of prefix array to valid MEX, and then we iterate through a array, while adding elements to set s1. At every a[i], we check whether it will increase the MEX on 0..i prefix. How? We iterate through all possible values (0 to max(a) + 1) and check if the current value was present in a suffix up to i. If it wasn't, then it can be MEX only if it's greater than MEX suffix up to previous index i - 1. If we find that value, then it's lowest value not present in suffix a[0..i].

The complexity of this it too big. It's like O(n * max(a) * logN) (due to using set to check if element exists in a till index i, and inserting elements to the set), which can result in more than 10^10 operations. How can we speed it up?

• I'm not sure I understand the problem. If the array has no 0 in it, you can divide it up however you like, all the subarrays will have a MEX of 0. Otherwise, the MEX of the array should be the same as the MEX of any subarrays you divide it into, so you need to look at the integers that are smaller than the MEX of the full array, and see how many subarrays you can make that each have all of these smaller integers. Am I understanding the problem right? Commented Jul 15 at 15:50
• @CrisLuengo If we were allowed to make only one segment (whole array), then I think MEX of it would be the best answer. It's because if we make segments in a way that every number is segment itself (for N length array we have N segments), then if the number is greater then 0, then MEX will always be 0. If its 0, then it will be 1. The problem is that when it becomes 1, then MEX won't be equal to other MEX'es. We will need to rearrange segments in a way that MEX is 1 in every sgment. It may not be possible. 1/2 Commented Jul 15 at 16:25
• But we see that if any element is 0, then it affects whole segment, which affects other segments, because the MEX'es need to be equal. Every segment affects any other segment, so I think the best answer is 1 segment that is whole array. But we need to have at least 2, and in fact, 2 segments should give optimal answer. So yes, if in every segment we will have all values that are lesser than MEX of whole array, it would give optimal answer. But it's not necessary that we will able to achieve this, that's why I would rather use one segment (two because they are required in problem statement)2/2 Commented Jul 15 at 16:32
• Right. So if the array’s MEX is 3, you need at least two subsegments that each have at least one 0, one 1, and one 2. You can check easily if you can make these segments by starting at the two ends, go right from the left end until you’ve seen each of those three numbers, then go left from the right end until you’ve seen each of those three numbers. Did your two searches cross? Then you can’t make the division. If they didn’t cross, you can even check to see if you can make a 3rd segment. In any case, you only need to compute the MEX of the full array once. Commented Jul 15 at 16:38
• It works. I computed MEX for whole array firstly by calculating frequency of every element, then I iterate over this data and as soon as I get value with frequency equal to 0, it's MEX. Whole solution is O(N + NlogN). Thanks! Commented Jul 15 at 19:14

You present code for a typical "challenge" submission without ever spelling out the problem in the source code.
What's more, you miss the opportunity to declare a suggestively named business function.

Given a preceding introduction of MinimumEXcluded number and the solution idea (in the source (I agree with the result two parts are enough)), mex_prefix/mex_suffix are appropriately named;
n, a&a_max pick up the problem statement's designations.

I think "the problematic part" starts before the annotation:

With an empty (sub)sequence, MEX is 0.
Extending a sequence with one value changes MEX exactly when the value is the former MEX value: no need for special handling of last or first value.

You use two iteration variables to iterate the sequence "from both ends"; one would do using n-1 - i instead of j.
Using both to control loop termination looks redundant.

Inside this loop, there is one loop per direction to find the smallest value still excluded. Both could start at MEX (mex_???fix[i-1/j+1) as all smaller values are known to be in the subsequence.
From C++20, there seems to be a contains() for sets which I'd find more readable here.

When i&j meet or "cross", one can stop updating any non-lower MEX.
If they are equal, both i&j are suitable split positions.
Simpler and halving "additional memory" required is to just establish mex_prefix[] and look for a match looping the other direction keeping a MEX for the suffix up-to-date.

I'd handle a suitable split position right in the loop, using return to terminate, and put "the none found handling" simply after the loop. (I see two ways to keep statement nesting in check here: one is breaking the loop as you did. Alternatively, move the handling out of the current procedure with an additional procedure, or to the one call site.)

I think I need to calculate the prefix and suffix array of MEX
As MEX cannot exceed n+1, one can map any larger value to n+2 (on input already). (This does not really speed up innermost loops termination as there is guaranteed to be a value missing before.)(Depending on representation, this would help keeping histogram memory occupancy small, too.)
In addition to a_max, one could establish an a_min:
If greater than 0, any split works, as well as when a_max is 0.