Mex Array

Problem Statement - link #

You are given an array A of length N. Let us define an array B as:

• B[i] = max(A[1], A[2], …, A[i]) for 1 ≤ i ≤ N.

mex of an array refers to the smallest missing non-negative integer of the array. For example, the mex of [0, 1, 2, 2] is 3, and the mex of [1, 2, 3, 4, 5] is 0.

You are allowed to rearrange the elements of the array A. Find the lexigraphically smallest array B which can be obtained.

Your Task:

The task is to complete the function mexArray() which takes an array A and its size N as input parameters and returns the lexigraphically smallest array B.

Examples #

Example 1:

Input: 
N = 3,
A = { 0,1,2 }
Output:
0 0 3
Explanation:
When A = { 1,2,0 }, we get the best
possible result.

Example 2:

Input:
N = 3,
A = { 0, 0, 1}
Output:
0 2 2
Explanation:
When A = { 1,0,0 }, we get the best
possible result.

Constraints #

• 1 ≤ N ≤ 10^5
• 0 ≤ A[i] ≤ N

Solutions #

class Solution{
	public:
	vector<int> mexArray(int n,int a[])
	{
		//code here
		sort(a, a+n, greater<int>());
		unordered_set<int> s(a, a+n);
		int temp = 0;
		vector<int> res(n);
		for(int i=0; i<n ;i++) {
		    if( temp < a[i]) {
		        res[i] = temp;
		    }
		    else {
		        while( !s.empty() && s.find(temp)!=s.end() ) {
		            temp++;
		        }
		        res[i] = temp;
		    }
		}
		return res;
	}
};