GFG : Maximum MEX from all subarrays of length K

Given an array arr[] consisting of N distinct integers and an integer K, the task is to find the maximum MEX from all subarray of length K.

The MEX is the smallest positive integer that is not present in the array.

Examples:

Input: arr[] = {3, 2, 1, 4}, K = 2
Output: 3
Explanation:
All subarrays having length 2 are {3, 2}, {2, 1}, {1, 4}.
In subarray {3, 2}, the smallest positive integer which is not present is 1.
In subarray {2, 1}, the smallest positive integer which is not present is 3.
In subarray {1, 4}, the smallest positive integer which is not present is 2.

Input: arr[] = {6, 1, 3, 2, 4}, K = 3
Output: 4
Explanation:
All subarrays having length 3 are {6, 1, 3}, {1, 3, 2}, {3, 2, 4}
In subarray {6, 1, 3}, the smallest positive integer which is not present is 2.
In subarray {1, 3, 2}, the smallest positive integer which is not present is 4.
In subarray {3, 2, 4}, the smallest positive integer which is not present is 1.

Solution :

#include <bits/stdc++.h>
using namespace std;

void maxMEX(int arr[], int N, int k) {
    set <int> st;
    int maxMex = 0;
    for(int i=1; i<=N; i++) {
        st.insert(i);
    }
    for(int i=0; i<N; i++) {
        st.erase(arr[i]);
        if(i >= k) {
            st.insert(arr[i-k]);
        }
        if(i >= k-1) {
            maxMex = max(maxMex, *st.begin());
        }
    }
    cout << maxMex << endl;
}

int main() {
    // Given array
    int arr[] = { 6, 1, 3, 2, 4 };
 
    // Given length of subarray
    int K = 3;
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    maxMEX(arr, N, K);
 
    return 0;
}