Find latest group of size m

Array Hash Table Binary Search Simulation

43.8% acceptance

Feb 25, 2026

679

144

Given an array arr that represents a permutation of numbers from 1 to n. We split arr into some number of chunks, and individually sort each chunk. After concatenating them, the result should equal the sorted array. You need to find the maximum number of chunks that can be made to sort the whole array. Note that this is a different problem than the classic "Max Chunks To Make Sorted" problem. In that problem, there are no duplicates.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_latest_step(arr: Vec<i32>, m: i32) -> i32 {
    // arr[i] = step at which bit i+1 is set
    // We simulate with a group-size tracking array
    let n = arr.len();
    let m = m as usize;
    // For each position, track group size by storing group size at left/right edge
    let mut size = vec![0usize; n + 2];
    let mut count_m = 0usize; // groups of size m
    let mut ans = -1i32;

    for (step, &pos) in arr.iter().enumerate() {
      let pos = pos as usize;
      let left_size = size[pos - 1];
      let right_size = size[pos + 1];
      let new_size = left_size + right_size + 1;

      // left neighbor group was size m, it will grow
      if left_size == m {
        count_m -= 1;
      }
      // right neighbor group was size m, it will grow
      if right_size == m {
        count_m -= 1;
      }
      // new merged group
      if new_size == m {
        count_m += 1;
      }

      // update boundaries of the new group
      size[pos - left_size] = new_size;
      size[pos + right_size] = new_size;
      size[pos] = new_size; // middle (optional but harmless)

      if count_m > 0 {
        ans = (step + 1) as i32;
      }
    }
    ans
  }
}