LeetCode 1562: Find Latest Group of Size M

Explanation

To solve this problem, we can simulate the process of setting bits in the binary string based on the given array arr. We can maintain a set to keep track of the groups of ones formed at each step. For each step, we update the binary string and check if there exists a group of ones of length m. If such a group exists, we update the latest step where this group was found.

Here is the step-by-step algorithm:

1. Initialize a binary string of size n with all zeros and a set to store the groups of ones.
2. Iterate over the array arr and update the binary string by setting the bit at position arr[i] to 1.
3. Update the set of groups by iterating over the binary string and identifying the groups of ones.
4. Check if there exists a group of ones of length m in the set. If yes, update the latest step where this group was found.
5. Return the latest step where a group of ones of length m was found or -1 if no such group exists.

The time complexity of this algorithm is O(n) where n is the length of the input array arr. The space complexity is also O(n) to store the binary string and the set of groups.

class Solution {
    public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        int[] binaryString = new int[n];
        Set<Integer> groups = new HashSet<>();
        int result = -1;
        
        for (int i = 0; i < n; i++) {
            binaryString[arr[i] - 1] = 1;
            groups.clear();
            int count = 0;
            
            for (int j = 0; j < n; j++) {
                if (binaryString[j] == 1) {
                    count++;
                    if (j == 0 || binaryString[j - 1] == 0) {
                        groups.add(count);
                    }
                } else {
                    count = 0;
                }
            }
            
            for (int groupSize : groups) {
                if (groupSize == m) {
                    result = i + 1;
                }
            }
        }
        
        return result;
    }
}