Find Latest Group of Size M
MediumUpdated: Aug 2, 2025
Practice on:
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 lengthexactly m. If no such group exists, return -1.
Examples
Example 1
Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation:
Step 1: "00 _1_ 00", groups: ["1"]
Step 2: "0010 _1_ ", groups: ["1", "1"]
Step 3: "_1_ 0101", groups: ["1", "1", "1"]
Step 4: "1 _1_ 101", groups: ["111", "1"]
Step 5: "111 _1_ 1", 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: "00 _1_ 00", groups: ["1"]
Step 2: "_1_ 0100", groups: ["1", "1"]
Step 3: "1010 _1_ ", groups: ["1", "1", "1"]
Step 4: "101 _1_ 1", groups: ["1", "111"]
Step 5: "1 _1_ 111", groups: ["11111"]
No group of size 2 exists during any step.
Constraints
n == arr.length1 <= m <= n <= 10^51 <= arr[i] <= n- All integers in
arrare distinct.
Solution
Method 1 – Union-Find with Length Tracking
Intuition
We need to efficiently track contiguous groups of 1s and their sizes as we flip bits in the order given by arr. By using an array to track the length of each group and a counter for groups of size m, we can update group sizes in constant time per step.
Approach
- Initialize an array
lengthof sizen+2to track the length of the group at each position (with sentinels at both ends). - Use a counter to track how many groups of size
mexist at each step. - For each step, set the bit at
arr[i]to 1:- Check the length of the group to the left and right.
- The new group size is
left + right + 1. - Update the
lengtharray at the boundaries. - Update the counter for groups of size
m(decrement for old groups, increment for new group if size matchesm).
- If at any step the counter is positive, record the step as the latest.
- Return the latest step found, or -1 if none.
Code
C++
class Solution {
public:
int findLatestStep(vector<int>& arr, int m) {
int n = arr.size(), res = -1, cnt = 0;
vector<int> length(n+2);
vector<int> count(n+1);
for (int i = 0; i < n; ++i) {
int pos = arr[i];
int left = length[pos-1], right = length[pos+1];
int total = left + right + 1;
length[pos-left] = length[pos+right] = total;
if (left > 0) count[left]--;
if (right > 0) count[right]--;
count[total]++;
if (count[m] > 0) res = i+1;
}
return res;
}
};
Go
func findLatestStep(arr []int, m int) int {
n := len(arr)
length := make([]int, n+2)
count := make([]int, n+1)
res := -1
for i, pos := range arr {
left, right := length[pos-1], length[pos+1]
total := left + right + 1
length[pos-left] = total
length[pos+right] = total
if left > 0 { count[left]-- }
if right > 0 { count[right]-- }
count[total]++
if count[m] > 0 { res = i+1 }
}
return res
}
Java
class Solution {
public int findLatestStep(int[] arr, int m) {
int n = arr.length, res = -1;
int[] length = new int[n+2];
int[] count = new int[n+1];
for (int i = 0; i < n; i++) {
int pos = arr[i];
int left = length[pos-1], right = length[pos+1];
int total = left + right + 1;
length[pos-left] = length[pos+right] = total;
if (left > 0) count[left]--;
if (right > 0) count[right]--;
count[total]++;
if (count[m] > 0) res = i+1;
}
return res;
}
}
Kotlin
class Solution {
fun findLatestStep(arr: IntArray, m: Int): Int {
val n = arr.size
val length = IntArray(n+2)
val count = IntArray(n+1)
var res = -1
for (i in arr.indices) {
val pos = arr[i]
val left = length[pos-1]
val right = length[pos+1]
val total = left + right + 1
length[pos-left] = total
length[pos+right] = total
if (left > 0) count[left]--
if (right > 0) count[right]--
count[total]++
if (count[m] > 0) res = i+1
}
return res
}
}
Python
class Solution:
def findLatestStep(self, arr: list[int], m: int) -> int:
n = len(arr)
length = [0] * (n+2)
count = [0] * (n+1)
res = -1
for i, pos in enumerate(arr):
left, right = length[pos-1], length[pos+1]
total = left + right + 1
length[pos-left] = length[pos+right] = total
if left > 0:
count[left] -= 1
if right > 0:
count[right] -= 1
count[total] += 1
if count[m] > 0:
res = i+1
return res
Rust
impl Solution {
pub fn find_latest_step(arr: Vec<i32>, m: i32) -> i32 {
let n = arr.len();
let mut length = vec![0; n+2];
let mut count = vec![0; n+1];
let mut res = -1;
for (i, &pos) in arr.iter().enumerate() {
let pos = pos as usize;
let left = length[pos-1];
let right = length[pos+1];
let total = left + right + 1;
length[pos-left] = total;
length[pos+right] = total;
if left > 0 { count[left] -= 1; }
if right > 0 { count[right] -= 1; }
count[total] += 1;
if count[m as usize] > 0 { res = (i+1) as i32; }
}
res
}
}
TypeScript
class Solution {
findLatestStep(arr: number[], m: number): number {
const n = arr.length;
const length = new Array(n+2).fill(0);
const count = new Array(n+1).fill(0);
let res = -1;
for (let i = 0; i < n; i++) {
const pos = arr[i];
const left = length[pos-1], right = length[pos+1];
const total = left + right + 1;
length[pos-left] = total;
length[pos+right] = total;
if (left > 0) count[left]--;
if (right > 0) count[right]--;
count[total]++;
if (count[m] > 0) res = i+1;
}
return res;
}
}
Complexity
- ⏰ Time complexity:
O(n), where n is the length of arr. Each step is constant time. - 🧺 Space complexity:
O(n), for the length and count arrays.