Meximum Array (Codeforces 1629C)
Tags: Greedy, two pointers

Mihai has just learned about the MEX concept and since he liked it so much, he decided to use it right away.Given an array $$$a$$$ of $$$n$$$ non-negative integers, Mihai wants to create a new array $$$b$$$ that is formed in the following way:While $$$a$$$ is not empty:   Choose an integer $$$k$$$ ($$$1 \leq k \leq |a|$$$).  Append the MEX of the first $$$k$$$ numbers of the array $$$a$$$ to the end of array $$$b$$$ and erase them from the array $$$a$$$, shifting the positions of the remaining numbers in $$$a$$$. But, since Mihai loves big arrays as much as the MEX concept, he wants the new array $$$b$$$ to be the lexicographically maximum. So, Mihai asks you to tell him what the maximum array $$$b$$$ that can be created by constructing the array optimally is.An array $$$x$$$ is lexicographically greater than an array $$$y$$$ if in the first position where $$$x$$$ and $$$y$$$ differ $$$x_i > y_i$$$ or if $$$|x| > |y|$$$ and $$$y$$$ is a prefix of $$$x$$$ (where $$$|x|$$$ denotes the size of the array $$$x$$$).The MEX of a set of non-negative integers is the minimal non-negative integer such that it is not in the set. For example, MEX({$$${1, 2, 3}$$$}) $$$= 0$$$ and MEX({$$${0, 1, 2, 4, 5}$$$}) $$$= 3$$$.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of elements in the array $$$a$$$.The second line of each test case contains $$$n$$$ non-negative integers $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$), where $$$a_i$$$ is the $$$i$$$-th integer from the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case print $$$m$$$ — the length of the maximum array $$$b$$$ Mihai can create, followed by $$$m$$$ integers denoting the elements of the array $$$b$$$.

Note: In the first test case, the lexicographically maximum array $$$b$$$ is obtained by selecting $$$k=5$$$, resulting in the $$$MEX$$$ of the whole array $$$a$$$. It is lexicographically maximum because an array starting with a smaller number than $$$4$$$ is lexicographically smaller, and choosing a $$$k<5$$$ would result in an array starting with a number smaller than $$$4$$$.In the second test case, there are two ways to obtain the maximum array: first selecting $$$k=6$$$, then $$$k=2$$$, or first selecting $$$k=7$$$ and then $$$k=1$$$.

Sample Inputs:
6
5
1 0 2 0 3
8
2 2 3 4 0 1 2 0
1
1
5
0 1 2 3 4
4
0 1 1 0
10
0 0 2 1 1 1 0 0 1 1

Sample Outputs:
1
4 
2
5 1 
1
0 
1
5 
2
2 2 
4
3 2 2 0

Solution (Python):
from collections import Counter
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    rem = Counter(a)
    c = set()
    ans = []
    mex = 0
    for i in range(n):
        c.add(a[i])
        while mex in c:
            mex += 1
        if rem[mex] == 0:
            ans.append(mex)
            c.clear()
            mex = 0
        rem[a[i]] -= 1
    print(len(ans))
    print(*ans)

Solution (Python):
def problemC(n, arr):
    count = {}
    for num in arr:
        if num not in count:
            count[num] = 0
        count[num] += 1
    mexNumber = 0
    numBag = set()
    ans = []
    for num in arr:
        numBag.add(num)
        while mexNumber in numBag:
            mexNumber += 1
        count[num] -= 1
        if mexNumber not in count or count[mexNumber] == 0:
            ans.append(str(mexNumber))
            numBag = set()
            mexNumber = 0
    if len(numBag) >= 1:
        ans.append(str(mexNumber))
    print(len(ans))
    print(*ans)
for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    problemC(n, arr)

Solution (Python):
def get_suffix_mex(a):
    b = a[::-1]
    ans = [0] * l
    mex = 0
    dc = set()
    for i in range(len(a)):
        while b[i] == mex or mex in dc:
            mex += 1
        dc.add(b[i])
        ans[i] = mex
    return ans[::-1]
for _ in range(int(input())):
    l = int(input())
    a = list(map(int, input().split()))
    suffix_mex = get_suffix_mex(a)
    ans = []
    p = 0
    while p < l:
        mex = 0
        dc = set()
        for i in range(p, len(a)):
            while a[i] == mex or mex in dc:
                mex += 1
            dc.add(a[i])
            if mex == suffix_mex[p]:
                ans.append(mex)
                p = i + 1
                break
    print(len(ans))
    print(*ans)