> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/find-latest-group-of-size-m.md).

# 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`

```java
class Solution {
    public int find(int[] parent, int node) {
        if (node != parent[node])
            parent[node] = find(parent, parent[node]);
        return parent[node];
    }

    public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        // Parent array for DSU
        int[] parent = new int[n];
        // Map of parent -> Size of group of that parent
        Map<Integer, Integer> map = new HashMap<>();
        char[] str = new char[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            str[i] = '0';
        }
        int ans = -1, countOfMGroups = 0;
        for (int i = 0; i < n; i++) {
            // Current parent
            int p = arr[i] - 1;
            // Initialising group size of this parent
            map.put(p, 1);
            str[p] = '1';
            // Joining process
            if (arr[i] - 2 >= 0 && str[arr[i] - 2] == '1') {
                int p1 = find(parent, arr[i] - 2);
                // This group size will be increased
                if (map.get(p1) == m)
                    countOfMGroups--;
                map.put(p1, map.get(p1) + 1);
                map.remove(p);
                parent[p] = p1;
                p = p1;
            }
            if (arr[i] < n && str[arr[i]] == '1') {
                int p2 = find(parent, arr[i]);
                // This group will be merged with others to form a bigger group
                if (map.get(p2) == m)
                    countOfMGroups--;
                map.put(p, map.get(p) + map.get(p2));
                map.remove(p2);
                parent[p2] = p;
            }
            if (map.get(p) == m)
                countOfMGroups++;
            if (countOfMGroups > 0)
                ans = i + 1;
        }
        return ans;
    }
}
```