Divide arrays

You are given an array $A$ of $N$ integers. Find the smallest index $i$ $(1\le i\le N-1)$ such that:

• $mex(A[1],A[2],..,A[i])=mex(A[i+1],A[i+2],...,A[N])$

If no such index exists, print $-1$.

$-1$

 Example:

Input: N = 5, A = {0, 2, 2, 3, 0}
Output: 1

Approach

Java

public class DivideArrays {
    public static void main(String args[])  {
        int N = 5;
        int[] A = { 0, 0, 2, 2, 3, 0 };

        int[] mexLeft = new int[N + 2];
        int[] mexRight = new int[N + 2];

        int[] seen = new int[100000 + 2];
        for (int i = 1; i <= N; i++) {
            // fill mexLeft
            seen[A[i]] = 1;
            mexLeft[i] = mexLeft[i - 1];
            while (seen[mexLeft[i]] == 1) {
                mexLeft[i] = mexLeft[i] + 1;
            }
        }

        seen = new int[100000 + 2];
        for (int i = N; i >= 1; i--) {
            // fill mexRight
            seen[A[i]] = 1;
            mexRight[i] = mexRight[i + 1];
            while (seen[mexRight[i]] == 1) {
                mexRight[i] = mexRight[i] + 1;
            }
        }

        // search smallest index
        int k = 1;
        while (k != N && mexLeft[k] != mexRight[k + 1]) {
            k++;
        }
        System.out.println((k == N) ? -1 : k);
    }
}

C++

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

int divideArrays(vector<int> A, int N)
{
    int mexLeft[N + 2];
    int mexRight[N + 2];

    for (int i = 0; i < N + 2; i++)
    {
        mexLeft[i] = 0;
        mexRight[i] = 0;
    }

    vector<int> seen(100002);
    for (int i = 1; i <= N; i++)
    {
        // fill mexLeft
        seen[A[i]] = 1;
        mexLeft[i] = mexLeft[i - 1];
        while (seen[mexLeft[i]] == 1)
        {
            mexLeft[i] = mexLeft[i] + 1;
        }
    }

    seen.clear();
    for (int i = N; i >= 1; i--)
    {
        // fill mexRight
        seen[A[i]] = 1;
        mexRight[i] = mexRight[i + 1];
        while (seen[mexRight[i]] == 1)
        {
            mexRight[i] = mexRight[i] + 1;
        }
    }

    // search smallest index
    int k = 1;
    while (k != N && mexLeft[k] != mexRight[k + 1])
    {
        k++;
    }
    if (k == N)
        return -1;
    else
        return k;
}
int main()
{
    int N = 5;
    vector<int> A = {0, 0, 2, 2, 3, 0};

    cout << divideArrays(A, N) << "\n";

    return 0;
}