MINMEX (Editorial)

1. The Fundamental Condition

For a value $v$ to be the $\text{MEX}$ of a subsequence, two things must be true:

1. Every number smaller than $v$ (0, 1, \dots, v-1) must be included in the subsequence.

2. The value $v$ itself must be absent.

Wait! If we only want the minimum possible $\text{MEX}$, we actually only need to satisfy the second condition. If we can form any subsequence of length $k$ that excludes $v$, then the $\text{MEX}$ of that subsequence will be at most $v$.

Crucial Observation: $v$ is a candidate for the minimum $\text{MEX}$ if there are enough elements in the array that are not equal to $v$ to fill a subsequence of length $k$.

2. The Mathematical Constraint

Let $f(v)$ be the frequency of value $v$ in the original array of size $n$.

• The number of elements available that are not $v$ is exactly n - f(v).

• If n - f(v) \ge k, then we can definitely pick $k$ elements such that $v$ is missing.

• In this case, the $\text{MEX}$ for length $k$ is $\le v$.

3. Monotonicity and the Suffix Trick

Notice that if a value $v$ is a candidate for length $k$, it is automatically a candidate for all lengths shorter than $k$ (e.g., k-1, k-2, \dots, 1).

To find the absolute minimum for each $k$:

1. For each $v$, calculate the maximum possible length K_{max} = n - f(v).

2. This $v$ is now a potential "ceiling" for the answer at k = K_{max}.

3. Since $v$ also works for all k < K_{max}, we simply need to take the best (minimum) $v$ available as we move from larger $k$ to smaller $k$.

Complexity : $O(n)$

#include <bits/stdc++.h>
using namespace std;

void solve() {   
    int n ;
    cin >> n ;
    vector <int> f(n + 3) ;
    for(int i = 0 ; i < n ; i ++) {
      int x ;
      cin >> x ;
      if(x <= n + 1) f[x] ++ ;
    }   
    vector <int> ans(n + 1 , n + 2) ;
    for(int v = 0 ; v <= n + 1 ; v ++) {
      ans[f[v]] = min(ans[f[v]] , v) ;
    }
    
    for(int i = 1 ; i <= n ; i ++) ans[i] = min(ans[i] , ans[i - 1]) ;
    for(int v = 1 ; v <= n ; v ++) cout << ans[n - v] << " " ;
    cout << "\n" ;   
    
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("output.txt", "w", stdout);
    // freopen("input.txt", "r", stdin);
    int t ;
    cin >> t ;
    while(t --) {
        solve() ;
    }
    return 0;
}