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.
Example 1:
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:
Input: team = [1], dist = 1 Output: 0 Explanation: There are no people who are not "it" to catch.
Example 3:
Input: team = [0], dist = 1 Output: 0 Explanation: There are no people who are "it" to catch people.
Constraints:
1 <= team.length <= 1050 <= team[i] <= 11 <= dist <= team.lengthProblem Overview: You are given an array where 1 represents a player who is "it" and 0 represents a normal player. A player who is "it" can catch a 0 within distance k. Each player can participate in at most one catch. The goal is to maximize the total number of catches.
Approach 1: Brute Force Search (O(n^2) time, O(1) space)
Iterate through the array and whenever you encounter a player with 1, scan the range [i-k, i+k] to find the nearest uncaught 0. If one exists, mark that index as used and increment the catch count. This directly simulates the rules but repeatedly scans nearby elements, which can lead to quadratic behavior in the worst case. The method works for small inputs but becomes inefficient when n grows large.
Approach 2: Greedy Two Pointers (O(n) time, O(1) space)
The optimal solution relies on a greedy observation: matching the closest possible players prevents future conflicts. First collect or implicitly traverse indices of 1 and 0. Use two pointers—one pointing to the next "it" player and the other to the next normal player. If the distance between them is within k, you record a catch and move both pointers forward. If the 0 is too far left, move the pointer for 0. If the 1 is too far left, move the pointer for 1. This greedy pairing ensures each player is used at most once and processes the array in a single linear pass.
This pattern appears often in array matching problems where elements must be paired under a distance or ordering constraint. The greedy decision works because choosing the nearest valid partner leaves the maximum flexibility for the remaining players. Implementations typically iterate through the array while maintaining two pointers, avoiding extra data structures.
Recommended for interviews: The greedy greedy approach using two pointers. Interviewers expect candidates to recognize the pairing constraint and reduce the problem to linear scanning. Mentioning the brute force approach first shows understanding of the rules, but implementing the O(n) greedy strategy demonstrates strong algorithmic thinking and optimization skills.
We can use two pointers i and j to point to the ghost and non-ghost people, initially i=0, j=0.
Then we traverse the array from left to right. When we encounter a ghost, i.e., team[i]=1, if j \lt n and team[j]=1 or i - j \gt dist, then move pointer j to the right in a loop. This means we need to find the first non-ghost person such that the distance between i and j does not exceed dist. If such a person is found, move pointer j one step to the right, indicating that we have caught this person, and increment the answer by one. Continue traversing the array until the entire array is processed.
Finally, return the answer.
The time complexity is O(n), where n is the length of the array team. The space complexity is O(1).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Range Scan | O(n^2) | O(1) | Useful for understanding the rules or when constraints are very small |
| Greedy Two Pointers | O(n) | O(1) | Best for large arrays; pairs closest valid players in one linear scan |
Maximum Number Of People That Can Be Caught In Tag • Owen Wu • 972 views views
Watch 1 more video solutions →Practice Maximum Number of People That Can Be Caught in Tag with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor