# Find Latest Group of Size M
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-latest-group-of-size-m)
Canonical: https://scaleengineer.com/dsa/problems/find-latest-group-of-size-m
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
---
## Problem
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`.

**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.

**Constraints:**

* `n == arr.length`
* `1 <= m <= n <= 105`
* `1 <= arr[i] <= n`
* All integers in `arr` are **distinct**.

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. At each step, we update the binary string by setting a bit to '1' and then scan the entire string to find if any group of '1's has a length of exactly `m`.
**Time:** O(n^2), where `n` is the length of `arr`. The main loop runs `n` times, and inside it, we scan the `bits` array, which takes O(n) time. This results in a total time complexity of O(n*n). · **Space:** O(n) to store the `bits` array representing the binary string.
**Pros:** Simple to understand and implement.; Directly follows the logic from the problem description.
**Cons:** Highly inefficient due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints.
### Explanation
We use a boolean array, `bits`, to represent the binary string, initially all set to `false` (representing '0's). We loop from step 1 to `n`. In each step `i`, we find the position `pos` from `arr[i-1]` and set the corresponding bit `bits[pos]` to `true`. After each bit flip, we perform a complete scan of the `bits` array. During the scan, we count consecutive `true` values. A sequence of `k` ones is considered a 'group' if it's surrounded by `false` values or the array boundaries. If we find any group whose length is exactly `m`, we update our answer, `latestStep`, with the current step number. Since we want the *latest* such step, we continue this process until all bits are set, and the final value of `latestStep` will be our answer.

```java
class Solution {
    public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        if (m > n) return -1;
        
        boolean[] bits = new boolean[n + 2]; // Use padding for easier boundary checks
        int latestStep = -1;
        
        for (int step = 0; step < n; step++) {
            int pos = arr[step];
            bits[pos] = true;
            
            // Check if any group of size m exists at this step
            boolean hasGroupOfM = false;
            int count = 0;
            // Iterate up to n+1 to handle a group ending at position n
            for (int i = 1; i <= n + 1; i++) { 
                if (bits[i]) {
                    count++;
                } else {
                    if (count == m) {
                        hasGroupOfM = true;
                        break; // Found a group, no need to check further for this step
                    }
                    count = 0;
                }
            }
            
            if (hasGroupOfM) {
                latestStep = step + 1;
            }
        }
        
        return latestStep;
    }
}
```
### Algorithm
- 1. Initialize a boolean array `bits` of size `n+2` (with padding for easier boundary checks) to all `false`.
- 2. Initialize a variable `latestStep` to `-1` to store the result.
- 3. Iterate through the input array `arr` from `step = 0` to `n-1`.
- 4. In each iteration, get the position `pos = arr[step]` and set `bits[pos] = true`.
- 5. After updating the `bits` array, perform a full scan to check for the existence of any group of size `m`.
- 6. To do this, iterate from `i = 1` to `n`, maintaining a `count` of consecutive `true` bits. When a `false` bit is encountered (or the end of the array is reached), it signifies the end of a group. Check if the `count` of this group is exactly `m`.
- 7. Keep a flag, `hasGroupOfM`, which is set to `true` if any group of size `m` is found in the current step's configuration.
- 8. If `hasGroupOfM` is `true` after the scan, update `latestStep` to the current step number (`step + 1`).
- 9. After the main loop finishes, return `latestStep`.

## Optimized Approach using Group Length Tracking
Instead of re-scanning the entire array at each step, we can maintain the lengths of the groups of ones in a more efficient way. When a new '1' is placed, it can merge with adjacent groups. We only need to track the lengths of these groups and how many groups of length `m` exist at any time.
**Time:** O(n), where `n` is the length of `arr`. We iterate through the input array once, and all operations inside the loop (array lookups and updates) are constant time. · **Space:** O(n) to store the `length` and `count` arrays, both of which are proportional to the input size `n`.
**Pros:** Very efficient, with a linear time complexity.; Easily handles the largest possible inputs within the time limits.
**Cons:** More complex to reason about and implement compared to the brute-force approach.; Requires two extra arrays, increasing space usage, though still linear.
### Explanation
This optimized approach avoids the expensive O(n) scan at each step. We use two auxiliary arrays: `length` and `count`. The `length` array stores the length of a group of ones at its boundaries. For example, if there is a group of ones from index `i` to `j`, we set `length[i] = length[j] = (j - i + 1)`. The `count` array acts as a frequency map, where `count[k]` stores how many groups of length `k` currently exist.

As we iterate through the steps, placing a '1' at position `pos`, we look at its neighbors `pos-1` and `pos+1`. The `length` values at these positions tell us the lengths of the adjacent groups. We use this information to calculate the length of the new, merged group. We then update the `count` array by decrementing the counts for the old groups that were just merged and incrementing the count for the new group. Finally, we update the `length` array at the new boundaries. By checking `count[m]` at each step, we can efficiently determine if a group of the target size exists and update our result accordingly.

```java
class Solution {
    public int findLatestStep(int[] arr, int m) {
        int n = arr.length;
        if (m > n) {
            return -1;
        }
        
        // length[i] stores the length of the group of 1s which has i as a boundary
        int[] length = new int[n + 2]; 
        // count[k] stores the number of groups of length k
        int[] count = new int[n + 1];
        
        int latestStep = -1;
        
        for (int step = 1; step <= n; step++) {
            int pos = arr[step - 1];
            
            int leftLen = length[pos - 1];
            int rightLen = length[pos + 1];
            
            int newLen = leftLen + rightLen + 1;
            
            // Update length at the boundaries of the new group
            length[pos - leftLen] = newLen;
            length[pos + rightLen] = newLen;
            
            // Update counts of groups
            if (leftLen > 0) {
                count[leftLen]--;
            }
            if (rightLen > 0) {
                count[rightLen]--;
            }
            count[newLen]++;
            
            // Check if there is any group of size m
            if (count[m] > 0) {
                latestStep = step;
            }
        }
        
        return latestStep;
    }
}
```
### Algorithm
- 1. Initialize an array `length` of size `n+2` with all zeros. `length[i]` will store the length of a group of ones if `i` is a boundary of that group.
- 2. Initialize an array `count` of size `n+1` with all zeros. `count[k]` will store the number of groups of length `k`.
- 3. Initialize `latestStep = -1`.
- 4. Iterate from `step = 1` to `n`:
  - a. Get the current position `pos = arr[step-1]` where a '1' is being placed.
  - b. Find the length of the group to the left, `leftLen = length[pos-1]`, and to the right, `rightLen = length[pos+1]`.
  - c. These two groups (if they exist) will be merged with the new '1'. Decrement the counts for their lengths: `count[leftLen]--` and `count[rightLen]--`.
  - d. Calculate the length of the new merged group: `newLen = leftLen + rightLen + 1`.
  - e. Increment the count for this new length: `count[newLen]++`.
  - f. Update the `length` array at the boundaries of this new group: `length[pos - leftLen] = newLen` and `length[pos + rightLen] = newLen`.
  - g. Check if `count[m]` is greater than 0. If it is, it means at least one group of length `m` exists at the current step, so update `latestStep = step`.
- 5. After the loop, return `latestStep`.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
private
  int[] size;
public
  int findLatestStep(int[] arr, int m) {
    int n = arr.length;
    if (m == n) {
      return n;
    }
    boolean[] vis = new boolean[n];
    p = new int[n];
    size = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
      size[i] = 1;
    }
    int ans = -1;
    for (int i = 0; i < n; ++i) {
      int v = arr[i] - 1;
      if (v > 0 && vis[v - 1]) {
        if (size[find(v - 1)] == m) {
          ans = i;
        }
        union(v, v - 1);
      }
      if (v < n - 1 && vis[v + 1]) {
        if (size[find(v + 1)] == m) {
          ans = i;
        }
        union(v, v + 1);
      }
      vis[v] = true;
    }
    return ans;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
private
  void union(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb) {
      return;
    }
    p[pa] = pb;
    size[pb] += size[pa];
  }
}

```

### JavaScript

```javascript
const findLatestStep = function ( arr , m ) { function find ( x ) { if ( p [ x ] !== x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } function union ( a , b ) { const pa = find ( a ); const pb = find ( b ); if ( pa === pb ) { return ; } p [ pa ] = pb ; size [ pb ] += size [ pa ]; } const n = arr . length ; if ( m === n ) { return n ; } const vis = Array ( n ). fill ( false ); const p = Array . from ({ length : n }, ( _ , i ) => i ); const size = Array ( n ). fill ( 1 ); let ans = - 1 ; for ( let i = 0 ; i < n ; ++ i ) { const v = arr [ i ] - 1 ; if ( v > 0 && vis [ v - 1 ]) { if ( size [ find ( v - 1 )] === m ) { ans = i ; } union ( v , v - 1 ); } if ( v < n - 1 && vis [ v + 1 ]) { if ( size [ find ( v + 1 )] === m ) { ans = i ; } union ( v , v + 1 ); } vis [ v ] = true ; } return ans ; };
```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  vector<int> size;
  int findLatestStep(vector<int> &arr, int m) {
    int n = arr.size();
    if (m == n)
      return n;
    p.resize(n);
    size.assign(n, 1);
    for (int i = 0; i < n; ++i)
      p[i] = i;
    int ans = -1;
    vector<int> vis(n);
    for (int i = 0; i < n; ++i) {
      int v = arr[i] - 1;
      if (v && vis[v - 1]) {
        if (size[find(v - 1)] == m)
          ans = i;
        unite(v, v - 1);
      }
      if (v < n - 1 && vis[v + 1]) {
        if (size[find(v + 1)] == m)
          ans = i;
        unite(v, v + 1);
      }
      vis[v] = true;
    }
    return ans;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
  void unite(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb)
      return;
    p[pa] = pb;
    size[pb] += size[pa];
  }
};

```

### Python

```python
class Solution:
    def findLatestStep(self, arr: List[int], m: int) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def union(a, b): pa, pb = find(a), find(b) if pa == pb: return p[pa] = pb size[pb] += size[pa] n = len(arr) if m == n: return n vis = [False] * n p = list(range(n)) size = [1] * n ans = - 1 for i, v in enumerate(arr): v -= 1 if v and vis[v - 1]: if size[find(v - 1)] == m: ans = i union(v, v - 1) if v < n - 1 and vis[v + 1]: if size[find(v + 1)] == m: ans = i union(v, v + 1) vis[v] = True return ans

```