Watch 2 video solutions for Maximum Number of People That Can Be Caught in Tag, a medium level problem involving Array, Greedy. This walkthrough by Owen Wu has 972 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |