Maximum number of people that can be caught in tag

Array Two Pointers Greedy

49.5% acceptance

Mar 31, 2026

You are playing a game of tag with your friends. In tag, people are divided into two teams: people who are "it", and people who are not "it". The people who are "it" want to catch as many people as possible who are not "it". You are given a 0-indexed integer array team containing only zeros (denoting people who are not "it") and ones (denoting people who are "it"), and an integer dist. A person who is "it" at index i can catch any one person whose index is in the range [i - dist, i + dist] (inclusive) and is not "it". Return the maximum number of people that the people who are "it" can catch.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn catch_maximum_amountof_people(team: Vec<i32>, dist: i32) -> i32 {
    // Greedy two-pointer: match "it" people (1s) with "not-it" people (0s)
    let mut zeros: Vec<usize> = Vec::new();
    let mut ones: Vec<usize> = Vec::new();
    for (i, &t) in team.iter().enumerate() {
      if t == 0 {
        zeros.push(i);
      } else {
        ones.push(i);
      }
    }
    let mut i = 0;
    let mut j = 0;
    let mut count = 0;
    while i < ones.len() && j < zeros.len() {
      if (ones[i] as i32 - zeros[j] as i32).abs() <= dist {
        count += 1;
        i += 1;
        j += 1;
      } else if ones[i] < zeros[j] {
        i += 1;
      } else {
        j += 1;
      }
    }
    count
  }
}