Problem

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 themaximum number of people that the people who are “it” can catch.

Examples

Example 1:

1
2
3
4
5
6
7
8

Input: team = [0,1,0,1,0], dist = 3
Output: 2
Explanation:
The person who is "it" at index 1 can catch people in the range [i-dist, i+dist] = [1-3, 1+3] = [-2, 4].
They can catch the person who is not "it" at index 2.
The person who is "it" at index 3 can catch people in the range [i-dist, i+dist] = [3-3, 3+3] = [0, 6].
They can catch the person who is not "it" at index 0.
The person who is not "it" at index 4 will not be caught because the people at indices 1 and 3 are already catching one person.

Example 2:

1
2
3
4

Input: team = [1], dist = 1
Output: 0
Explanation:
There are no people who are not "it" to catch.

Example 3:

1
2
3

Input: team = [0], dist = 1
Output: 0
Explanation: There are no people who are "it" to catch people.

Constraints:

  • 1 <= team.length <= 10^5
  • 0 <= team[i] <= 1
  • 1 <= dist <= team.length

Solution

Method 1 – Greedy Two-Pointer

Intuition

To maximize the number of people caught, match each person who is “it” to the nearest available person who is not “it” within the allowed distance. Use two pointers to efficiently pair “it” and “not it” people.

Approach

  1. Collect the indices of all people who are “it” and all who are not “it”.
  2. Use two pointers to iterate through both lists:
    • For each “it” person, move the “not it” pointer forward until the person is within the catchable range.
    • If a match is found, increment the answer and move both pointers forward.
    • Otherwise, move the pointer that is behind.
  3. Return the total number of matches found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int catchMaximumPeople(vector<int>& team, int dist) {
        vector<int> its, notits;
        for (int i = 0; i < team.size(); ++i) {
            if (team[i] == 1) its.push_back(i);
            else notits.push_back(i);
        }
        int ans = 0, i = 0, j = 0;
        while (i < its.size() && j < notits.size()) {
            if (abs(its[i] - notits[j]) <= dist) {
                ans++;
                i++; j++;
            } else if (its[i] < notits[j]) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func catchMaximumPeople(team []int, dist int) int {
    its, notits := []int{}, []int{}
    for i, v := range team {
        if v == 1 {
            its = append(its, i)
        } else {
            notits = append(notits, i)
        }
    }
    ans, i, j := 0, 0, 0
    for i < len(its) && j < len(notits) {
        if abs(its[i]-notits[j]) <= dist {
            ans++
            i++
            j++
        } else if its[i] < notits[j] {
            i++
        } else {
            j++
        }
    }
    return ans
}
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int catchMaximumPeople(int[] team, int dist) {
        List<Integer> its = new ArrayList<>();
        List<Integer> notits = new ArrayList<>();
        for (int i = 0; i < team.length; i++) {
            if (team[i] == 1) its.add(i);
            else notits.add(i);
        }
        int ans = 0, i = 0, j = 0;
        while (i < its.size() && j < notits.size()) {
            if (Math.abs(its.get(i) - notits.get(j)) <= dist) {
                ans++;
                i++;
                j++;
            } else if (its.get(i) < notits.get(j)) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun catchMaximumPeople(team: IntArray, dist: Int): Int {
        val its = mutableListOf<Int>()
        val notits = mutableListOf<Int>()
        for (i in team.indices) {
            if (team[i] == 1) its.add(i) else notits.add(i)
        }
        var ans = 0
        var i = 0
        var j = 0
        while (i < its.size && j < notits.size) {
            if (kotlin.math.abs(its[i] - notits[j]) <= dist) {
                ans++
                i++
                j++
            } else if (its[i] < notits[j]) {
                i++
            } else {
                j++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def catchMaximumPeople(self, team: list[int], dist: int) -> int:
        its = [i for i, v in enumerate(team) if v == 1]
        notits = [i for i, v in enumerate(team) if v == 0]
        ans = i = j = 0
        while i < len(its) and j < len(notits):
            if abs(its[i] - notits[j]) <= dist:
                ans += 1
                i += 1
                j += 1
            elif its[i] < notits[j]:
                i += 1
            else:
                j += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn catch_maximum_people(team: Vec<i32>, dist: i32) -> i32 {
        let mut its = vec![];
        let mut notits = vec![];
        for (i, &v) in team.iter().enumerate() {
            if v == 1 {
                its.push(i as i32);
            } else {
                notits.push(i as i32);
            }
        }
        let (mut i, mut j, mut ans) = (0, 0, 0);
        while i < its.len() && j < notits.len() {
            if (its[i] - notits[j]).abs() <= dist {
                ans += 1;
                i += 1;
                j += 1;
            } else if its[i] < notits[j] {
                i += 1;
            } else {
                j += 1;
            }
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    catchMaximumPeople(team: number[], dist: number): number {
        const its: number[] = [], notits: number[] = [];
        for (let i = 0; i < team.length; i++) {
            if (team[i] === 1) its.push(i);
            else notits.push(i);
        }
        let ans = 0, i = 0, j = 0;
        while (i < its.length && j < notits.length) {
            if (Math.abs(its[i] - notits[j]) <= dist) {
                ans++;
                i++;
                j++;
            } else if (its[i] < notits[j]) {
                i++;
            } else {
                j++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of team, since each index is processed once.
  • 🧺 Space complexity: O(n), for storing the indices of “it” and “not it” people.