Leetcode 1562. Find Latest Group of Size M

https://leetcode.com/problems/find-latest-group-of-size-m/description/

Notes:

This question can be solved by greedy.

When one bit is labeled as 1, then we need to check its two sides: the left and the right. 

if the left has been labeled with a length of 1's, then we need to combine it with the current 1;

for the right, we need to do the same thing.

So we need a vector to memorize the length of 1's at each positions. Do we need to memorize this for all positions? 

The answer is no. We just need to record this information at the two end positions for a group of 1's.

For example, if we have 1's at position (or index) 2, 3, 4, we just need to label len[2] = len[4] = 3. Based on the question, all the element is valid, so 2, 3, 4 will not appear again. Therefore, we just need to deal with the boundaries of each group of 1's. To this example, the boundaries are 2 and 4.

Since the question is asking for the last time sting having length of 1 with m, we need a hash map to record the information for this. Since all the keys are in the range of 0 to n, then we can use a vector as a hash map.

See the code below:

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