Discover the Prefix-MEX Array for given Array

Given an array A[] of N parts, 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
Clarification: Within the array A, parts 
Until 1st index, parts are [1] and mex until 1st index is 0.
Until 2nd index, parts are [1, 0] and mex until 2nd index is 2.
Until third index, parts are [ 1, 0, 2] and mex until third index is 3.
Until 4th index, parts are [ 1, 0, 2, 4] and mex until 4th index is 3.
Until fifth index, parts are [ 1, 0, 2, 4, 3] and mex until fifth index is 5.
So our closing array B could be [0, 2, 3, 3, 5].

Enter: A[] = [ 1, 2, 0 ]
Output: [ 0, 0, 3 ]
Clarification: Within the array A, parts 
Until 1st index, parts are [1] and mex until 1st index is 0.
Until 2nd index, parts are [1, 2] and mex until 2nd index is 0.
Until third index, parts are [ 1, 2, 0] and mex until third index is 3.
So our closing array B could be [0, 0, 3].

Naive Method: The only strategy to remedy the issue is:

For every component 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 thought:

• 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 Method: This method relies on the utilization of Set knowledge construction.

A set shops knowledge in sorted order. We are able to reap the benefits of that and retailer all of the non-negative integers until the utmost worth of the array. Then traverse by way of every array component and take away the visited knowledge from set. The smallest remaining component would be the MEX for that index.

Comply with the steps beneath to implement the thought:

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

Beneath is the implementation of the above method. 

Time Complexity: O(N * log N )

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

Auxiliary House: O(N)