1562. 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 also given an integer m. Find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1’s 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.

• dp solution

class Solution {
public:
    int findLatestStep(vector<int>& arr, int m) {
        int n = arr.size(), res = -1;
        vector<int> merge(n + 2), count(n + 1);
        for(int i = 0; i < n; i++) {
            int a = arr[i], left = merge[a-1], right = merge[a+1];
            merge[a] = merge[a-left] = merge[a+right] = right + left + 1;
            count[left]--;
            count[right]--;
            count[merge[a]]++;
            if(count[m])
                res = i + 1;
        }
        return res;
    }
};

• merge interval

class Solution {
    int merge(map<int,int>& mp, int pos, int& m) {
        auto it = mp.lower_bound(pos);
        bool wasM = false;
        if(it != end(mp) and it->first == pos + 1) {
            auto nxt = it;
            if(nxt->second - nxt->first + 1 == m)
                wasM = true;
            it = mp.insert({pos, nxt->second}).first;
            mp.erase(nxt);
        } else {
            it = mp.insert({pos, pos}).first;
        }
        
        if(it != begin(mp)) {
            auto prv = prev(it);
            if(prv->second + 1 == it->first) {
                auto nxt = it;
                it = prv;
                if(it->second - it->first + 1 == m)
                    wasM = true;
                it->second = nxt->second;
                mp.erase(nxt);
            }
        }
        if(it->second - it->first + 1 == m)
            return 1;
        if(wasM)
            return -1;
        return 0;
    }
public:
    int findLatestStep(vector<int>& arr, int m) {
        map<int, int> mp;
        int res = -1;
        for(int i = 0; i < arr.size(); i++) {
            int merged = merge(mp, arr[i], m);
            if(merged == 1)
                res = i + 1;
            else if(merged == -1)
                res = i;
        }
        return res;
    }
};