Find Latest Group of Size M

Find Latest Group of Size M

Given an array arr that represents a permutation of numbers from 1 to n. You have a binary string of size n that initially has all its bits set to zero.

At each step i (assuming both the binary string and arr are 1-indexed) from 1 to n, the bit at position arr[i] is set to 1. You are given an integer m and you need to find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1s such that it cannot be extended in either direction.

Return the latest step at which there exists a group of ones of length exactly m. If no such group exists, return -1.

 

Example 1:

Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.

Example 2:

Input: arr = [3,1,5,4,2], m = 2
Output: -1
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "10100", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "10111", groups: ["1", "111"]
Step 5: "11111", groups: ["11111"]
No group of size 2 exists during any step.

Example 3:

Input: arr = [1], m = 1
Output: 1

Example 4:

Input: arr = [2,1], m = 2
Output: 2

 

Constraints:

• n == arr.length
• 1 <= n <= 10^5
• 1 <= arr[i] <= n
• All integers in arr are distinct.
• 1 <= m <= arr.length

 

// class Solution {

// public:

//     int findLatestStep(vector<int>& arr, int m) {

//         int ans=-1,n=arr.size(),cnt=0;

//         vector<int> left(n+2,0),right(n+2,0);

//         for(int i=0;i<n;++i)

//         {

//             int k=arr[i];

//             int r=left[k+1],l=right[k-1];

//             if(l==m)--cnt;

//             if(r==m)--cnt;

            

//             if(l+1+r==m)++cnt;

//             if(l==0)left[k]=1+r;

//             else

//                 left[k-l]=l+1+r;

//             if(r==0)right[k]=l+1;

//             else

//                 right[k+r]=l+1+r;

//             if(cnt>0)ans=i+1;

//         }

//         return ans;

//     }

// };

class Solution {

public:

    int n;

    vector<int> par, sz, szcount;

    

    int p(int a) {

        if (par[a] == a) return a;

        par[a] = p(par[a]);

        return par[a];

    }

    

    int same(int a, int b) {

        return p(a) == p(b);

    }

    

    void join(int a, int b) {

        if (a < 0 || b < 0 || a >= n || b >= n || sz[a] == 0 || sz[b] == 0) return;

        

        if (same(a, b)) return;

        int sa = sz[p(a)], sb = sz[p(b)];

        szcount[sa]--; szcount[sb]--; szcount[sa+sb]++;

        sz[p(a)] = sa+sb;

        par[p(b)] = p(a);

    }

    

    int findLatestStep(vector<int>& arr, int k) {

        // dsu.

        n = arr.size();

        par.resize(n, -1); sz.resize(n, 0); szcount.resize(n+1, 0);

        for (int i = 0; i < n; i++) par[i] = i;

        

        szcount[0] = n;

        

        int i = 0, ans = -1;

        for (int a : arr) {

            a--;

            sz[a] = 1;

            szcount[0]--; szcount[1]++;

            join(a, a-1);

            join(a, a+1);

            

            if (szcount[k]) ans = i+1;

            i++;

        }

        return ans;

    }

};