Construct MEX array from the given array
Given an array arr[] having N distinct positive elements, the task is to generate another array B[] such that, for every ith index in the array, arr[], B[i] is the minimum positive number missing from arr[] excluding arr[i].
Examples:
Input: arr[] = {2, 1, 5, 3}
Output: B[] = {2, 1, 4, 3}
Explanation: After excluding the arr[0], the array is {1, 5, 3}, and the minimum positive number which is not present in this array is 2. Therefore, B[0] = 2. Similarly, after excluding arr[1], arr[2], arr[3], the minimum positive numbers which are not present in the array are 1, 4 and 3, respectively. Hence, B[1] = 1, B[2] = 4, B[3] = 3.Input: arr[] = {1, 9, 2, 4}
Output: B[] = {1, 3, 2, 3}
Naive Approach: The simplest approach to solve this problem is to traverse the array arr[] and for every index i, initialize an array hash[] and for every index j ( where j ? i), update hash[arr[j]] =1. Now traverse array hash[] from index 1 and find the minimum index k for which hash[k] = 0 and update B[i] = k. Finally, print the array B[] after completing the above step.
Time Complexity: O(N2) where N is the length of the given array.
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to calculate MEX of the array arr[] and traverse the array arr[]. If arr[i] is less than MEX of the array arr[] then MEX excluding this element will be arr[i] itself, and if arr[i] is greater than MEX of array A[] then MEX of the array will not change after excluding this element.
Follow the steps below to solve the problem:
- Initialize an array, say hash[], to store whether the value i is present in the array arr[] or not. If i is present hash[i] = 1 else hash[i] = 0.
- Initialize a variable MexOfArr to store MEX of array arr[] and traverse array hash[] from 1 to find the minimum index j for which hash[j] = 0, which implies that the value j is not present in the array arr[] and store MexOfArr = j.
- Now traverse the array, arr[] and if arr[i] is less than MexOfArr, then store B[i] = arr[i] else B[i] = MexOfArr.
- After completing the above steps, print elements of the array B[] as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define MAXN 100001 // Function to construct array B[] that // stores MEX of array A[] excluding A[i] void constructMEX( int arr[], int N) { // Stores elements present in arr[] int hash[MAXN] = { 0 }; // Mark all values 1, if present for ( int i = 0; i < N; i++) { hash[arr[i]] = 1; } // Initialize variable to store MEX int MexOfArr; // Find MEX of arr[] for ( int i = 1; i < MAXN; i++) { if (hash[i] == 0) { MexOfArr = i; break ; } } // Stores MEX for all indices int B[N]; // Traverse the given array for ( int i = 0; i < N; i++) { // Update MEX if (arr[i] < MexOfArr) B[i] = arr[i]; // MEX default else B[i] = MexOfArr; } // Print the array B for ( int i = 0; i < N; i++) cout << B[i] << ' ' ; } // Driver Code int main() { // Given array int arr[] = { 2, 1, 5, 3 }; // Given size int N = sizeof (arr) / sizeof (arr[0]); // Function call constructMEX(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ static int MAXN = 100001 ; // Function to construct array // B[] that stores MEX of array // A[] excluding A[i] static void constructMEX( int arr[], int N) { // Stores elements present // in arr[] int hash[] = new int [MAXN]; for ( int i = 0 ; i < N; i++) { hash[i] = 0 ; } // Mark all values 1, if // present for ( int i = 0 ; i < N; i++) { hash[arr[i]] = 1 ; } // Initialize variable to // store MEX int MexOfArr = 0 ; // Find MEX of arr[] for ( int i = 1 ; i < MAXN; i++) { if (hash[i] == 0 ) { MexOfArr = i; break ; } } // Stores MEX for all // indices int B[] = new int [N]; // Traverse the given array for ( int i = 0 ; i < N; i++) { // Update MEX if (arr[i] < MexOfArr) B[i] = arr[i]; // MEX default else B[i] = MexOfArr; } // Print the array B for ( int i = 0 ; i < N; i++) System.out.print(B[i] + " " ); } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 2 , 1 , 5 , 3 }; // Size of array int N = arr.length; // Function call constructMEX(arr, N); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the # above approach MAXN = 100001 # Function to construct # array B[] that stores # MEX of array A[] excluding # A[i] def constructMEX(arr, N): # Stores elements present # in arr[] hash = [ 0 ] * MAXN # Mark all values 1, # if present for i in range (N): hash [arr[i]] = 1 # Initialize variable to # store MEX MexOfArr = 0 # Find MEX of arr[] for i in range ( 1 , MAXN): if ( hash [i] = = 0 ): MexOfArr = i break # Stores MEX for all # indices B = [ 0 ] * N # Traverse the given array for i in range (N): # Update MEX if (arr[i] < MexOfArr): B[i] = arr[i] # MEX default else : B[i] = MexOfArr # Print array B for i in range (N): print (B[i], end = " " ) # Driver Code if __name__ = = '__main__' : # Given array arr = [ 2 , 1 , 5 , 3 ] # Given size N = len (arr) # Function call constructMEX(arr, N) # This code is contributed by Mohit Kumar 29 |
C#
// C# program for the above approach using System; class GFG{ static int MAXN = 100001; // Function to construct array // B[] that stores MEX of array // A[] excluding A[i] static void constructMEX( int [] arr, int N) { // Stores elements present // in arr[] int [] hash = new int [MAXN]; for ( int i = 0; i < N; i++) { hash[i] = 0; } // Mark all values 1, if // present for ( int i = 0; i < N; i++) { hash[arr[i]] = 1; } // Initialize variable to // store MEX int MexOfArr = 0; // Find MEX of arr[] for ( int i = 1; i < MAXN; i++) { if (hash[i] == 0) { MexOfArr = i; break ; } } // Stores MEX for all // indices int [] B = new int [N]; // Traverse the given array for ( int i = 0; i < N; i++) { // Update MEX if (arr[i] < MexOfArr) B[i] = arr[i]; // MEX default else B[i] = MexOfArr; } // Print the array B for ( int i = 0; i < N; i++) Console.Write(B[i] + " " ); } // Driver Code public static void Main() { // Given array arr[] int [] arr = { 2, 1, 5, 3 }; // Size of array int N = arr.Length; // Function call constructMEX(arr, N); } } // This code is contributed by code_hunt |
Javascript
<script> // Javascript program for the above approach var MAXN = 100001; // Function to construct array B[] that // stores MEX of array A[] excluding A[i] function constructMEX(arr, N) { // Stores elements present in arr[] var hash = Array(MAXN).fill(0); // Mark all values 1, if present for ( var i = 0; i < N; i++) { hash[arr[i]] = 1; } // Initialize variable to store MEX var MexOfArr; // Find MEX of arr[] for ( var i = 1; i < MAXN; i++) { if (hash[i] == 0) { MexOfArr = i; break ; } } // Stores MEX for all indices var B = Array(N); // Traverse the given array for ( var i = 0; i < N; i++) { // Update MEX if (arr[i] < MexOfArr) B[i] = arr[i]; // MEX default else B[i] = MexOfArr; } // Print the array B for ( var i = 0; i < N; i++) document.write( B[i] + ' ' ); } // Driver Code // Given array var arr = [2, 1, 5, 3]; // Given size var N = arr.length; // Function call constructMEX(arr, N); </script> |
2 1 4 3
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us