Discover the Prefix-MEX Array for given Array

Given an array A[] of N components, the duty is to create a Prefix-MEX array for this given array. Prefix-MEX array B[] of an array A[] is created such that MEX of A[0] until A[i] is B[i]. 

MEX of an array refers back to the smallest lacking non-negative integer of the array.

Examples:

Enter: A[] = {1, 0, 2, 4, 3}
Output: 0 2 3 3 5
Rationalization: Within the array A, components 
Until 1st index, components are [1] and mex until 1st index is 0.
Until 2nd index, components are [1, 0] and mex until 2nd index is 2.
Until third index, components are [ 1, 0, 2] and mex until third index is 3.
Until 4th index, components are [ 1, 0, 2, 4] and mex until 4th index is 3.
Until fifth index, components are [ 1, 0, 2, 4, 3] and mex until fifth index is 5.
So our last array B can be [0, 2, 3, 3, 5].

Enter: A[] = [ 1, 2, 0 ]
Output: [ 0, 0, 3 ]
Rationalization: Within the array A, components 
Until 1st index, components are [1] and mex until 1st index is 0.
Until 2nd index, components are [1, 2] and mex until 2nd index is 0.
Until third index, components are [ 1, 2, 0] and mex until third index is 3.
So our last array B can be [0, 0, 3].

Naive Strategy: The only option to remedy the issue is:

For every aspect at i^th (0 ≤ i < N)index of the array A[], discover MEX from 0 to i and retailer it at B[i].

Comply with the steps talked about beneath to implement the concept:

• Iterate over the array from i = 0 to N-1:
  • For each i^th index in array A[]: 
• Return the resultant array B[] on the finish.

Time Complexity: O(N²)
Auxiliary House: O(N)

Environment friendly Strategy: This strategy relies on the utilization of Set information construction.

A set shops information in sorted order. We will benefit from that and retailer all of the non-negative integers until the utmost worth of the array. Then traverse by means of every array aspect and take away the visited information from set. The smallest remaining aspect would be the MEX for that index.

Comply with the steps beneath to implement the concept:

• Discover the utmost aspect of the array A[].
• Create a set and retailer the numbers from 0 to the utmost aspect within the set.
• Traverse by means of the array from i = 0 to N-1: 
  • For every aspect, erase that aspect from the set.
  • Now discover the smallest aspect remaining within the set.
  • That is the prefix MEX for the i^th aspect. Retailer this worth within the resultant array.
• Return the resultant array because the required reply.

Under is the implementation of the above strategy. 

Time Complexity: O(N * log N )

• O(N) for iterating the vector, and 
• O(log N) for inserting and deleting the aspect from the set.

Auxiliary House: O(N)