Mex Subarray Count In C++

In this tutorial, we will explore the MEX Subarray Count function in C++ along with an illustrative example and advantages.

When provided with an array of length N, where each element is within the range [0, N-1], indicating a permutation, the current objective is to determine the count of subarrays where the Minimum Excludant (MEX) exceeds the median.

The MEX, which stands for Minimum EXcluded, refers to the smallest integer not present in the given array.

Examples:

Input: N=4, arr=[0, 2, 1, 3]

Output: 4

Explanation: The subarrays with a Minimum Excludant (MEX) higher than the Median include [0], [0, 2], [0, 2, 1], and [0, 2, 1, 3].

Input: N=4, arr=[1, 0]

Output: 2

The arrays that have a Minimum Excludant (MEX) higher than the Median are [0] and [1, 0].

MEX Subarray Count using Two Pointers:

Firstly, it's notable that the Minimum EXclusion (MEX) value within each subarray ranges from 0 to N. When determining the solution for a specific MEX value, consider the following approach. For a given MEX value, identify 'l' as the index of the leftmost number, ranging from 0 to mex-1, and 'r' as the index of the rightmost number, also ranging from 0 to mex-1. Define 'curr' as (r-l)+1, representing the current subarray length. The count of subarrays can be computed using various methods when curr is less than or equal to 2MEX. In such cases, the Median (MED) of the subarray, denoted as arr[l..r], falls within the range [0..MEX-1]. If curr exceeds 2MEX, it indicates a higher MED for the subarray.

Follow the steps to solve the problem:

• ✅ Create an index and frequency array to hold the index and frequency of elements. The number of subarrays with MEX higher than the median should be stored in the ans
• ✅ Preserve the two pointers, l and r , which hold the index of the first, second, third, and so forth. The r and mex-1 represent the right-most numbers 0, 1, 2,... mex-1.
• ✅ While mex is less than or equal to N, perform a loop:
• ✅ Determine the current subarray's size using curr=(r-l)+1 and set len=2*mex .
• ✅ The answer is updated using certain formulas if curr<=len , which indicates that the subarray's median is less than mex.
• ✅ The response won't be updated if not.
• ✅ Update mex, l, and r.
• ✅ Answer back.

Example:

Below is the execution of the aforementioned method:

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> a, int N) {
vector<int> idx(N + 2);
vector<int> frq(N + 2, 0);
for (int i = 0; i < N; i++) {
idx[a[i]] = i;
}
if (N == 1) {
return 1;
}
int ans = 0; // Initialize the answer to 0
int mex = 1; // Initialize mex to 1
int l = idx[0]; // Initialize l to the index of 0
int r = idx[0]; // Initialize r to the index of 0
frq[0] = 1;	 // Mark the frequency of 0 as 1
while (mex <= N) {
int num1 = 0, num2 = 0;
int len = mex * 2;
int curr = (r - l + 1);
int op = len - curr;
if (mex == N) {
num1 = l;
num2 = (N - 1) - r;
} else {
if (idx[mex] < l) {
num1 = (l - idx[mex]) - 1;
num2 = (N - 1) - r;
} else {
num1 = l;
num2 = (idx[mex] - r) - 1;
}
}
if (op == 0) {
ans++;
} else if (op > 0) {
num1 = min(op, num1);
num2 = min(op, num2);
if (num1 > num2)
swap(num1, num2);
int ext = (num2 + 1) * (min((op - num2) + 1, num1 + 1));
int rem = max(0, num1 - (op - num2));
int m = num2;
int x = max(0, m - rem);
int ext1 = (m * (m + 1)) / 2;
int ext2 = (x * (x + 1)) / 2;
ans = ans + ext + (ext1 - ext2);
}
if (mex == N)
break;
if (idx[mex] < l) {
l--;
while (l != idx[mex]) {
frq[a[l]] = 1;
l--;
}
frq[a[l]] = 1;
} else if (idx[mex] > r) {
r++;
while (r != idx[mex]) {
frq[a[r]] = 1;
r++;
}
frq[a[r]] = 1;
}
while (frq[mex] != 0) {
mex++;
}
}
return ans;
}
int main() {
int N = 4;
vector<int> arr = {0, 2, 1, 3};
cout << solve(arr, N);
}

Output:

Complexity Analysis:

Time Complexity: O(N)

Auxiliary Space: O(N)

Benefits of MEX Subarray Count in C++

The Minimum Excluded Element is commonly called "MEX" in a set or array. When we discuss the "MEX Subarray Count", we may be referring to determining how many subarrays in a particular array have a minimum excluded element. But in the absence of further information or a particular problem statement, allow us to list some possible advantages of handling MEX subarray count-related issues:

• ✅ Algorithmic Difficulties: MEX subarray count problems frequently pose intriguing algorithmic puzzles that call for effective solutions. Working on such difficulties improves our ability to solve problems and think algorithmically.
• ✅ Knowing How to Manipulate Arrays: A solid grasp of array manipulation techniques is necessary when working with MEX subarray count problems. We might need to track specific properties, iterate over the array, and dynamically update values.
• ✅ Application of Prefix Sum Techniques: Using prefix sum or other array transformation techniques may be necessary to solve some MEX subarray count difficulties. It offers a chance to use and comprehend these methods in a real-world setting.
• ✅ Effective Time and Space Complexity: Resolving MEX subarray count issues frequently calls for the efficient use of time and space complexity. It tests our ability to create effective algorithms that can process big datasets in a reasonable amount of time and memory.
• ✅ Knowing the concept of MEX (Minimum Excluded Element): We can better understand the idea of the minimum excluded element in a set or array by solving MEX-related tasks. This idea appears frequently in a variety of mathematical and computer science issues.
• ✅ Use of Data Structures: We may need to employ other data structures, including arrays, sets, or other complex data structures, depending on the particular problem. It lets us experiment and use different data structures according to the situation's needs.
• ✅ Coding Exercise: Solving MEX subarray count issues is a great way to gain experience with coding. It strengthens our comprehension of basic C++ programming constructs and helps us become a better implementer.
• ✅ Programming in competition: Many MEX-related issues come up in programming competitions. Knowledge of these kinds of challenges can help us to tackle them in coding competitions.

Recall that the benefits differ based on the scenario and problem at hand. Engaging in MEX subarray count challenges is a method to enhance your understanding of algorithmic concepts within the realm of arrays and sets. Solving each problem enhances our overall programming skills and problem-solving capabilities.