Skip to main content
Talentd

Maximum Number of People That Can Be Caught in Tag - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedy7 min read
Practice this problem

Problem Statement

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 <= 105
  • 0 <= team[i] <= 1
  • 1 <= dist <= team.length

Approach Overview

Problem 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.

Solution

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).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Range ScanO(n^2)O(1)Useful for understanding the rules or when constraints are very small
Greedy Two PointersO(n)O(1)Best for large arrays; pairs closest valid players in one linear scan

Video Solution

Maximum Number Of People That Can Be Caught In Tag • Owen Wu • 974 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Maximum Number of People That Can Be Caught in Tag easy or hard?
Maximum Number of People That Can Be Caught in Tag is generally classified as a Medium problem. The challenge is recognizing the greedy pairing strategy and implementing the two‑pointer traversal efficiently.
Maximum Number of People That Can Be Caught in Tag Python/Java solution
Implement the greedy two‑pointer logic in Python or Java by scanning the array and maintaining two indices for the next 1 and 0. When their distance is within k, increment the answer and advance both pointers. Otherwise move the pointer that is too far behind. The implementation runs in O(n) time.
How to solve Maximum Number of People That Can Be Caught in Tag in O(n)?
Traverse the array with two pointers representing the next "it" player and the next normal player. Compare their indices: if the distance is ≤ k, record a catch and advance both pointers. If the normal player is too far left, move that pointer forward; if the "it" player is too far left, move its pointer. Each element is processed once, giving O(n) time.
What is the best approach for Maximum Number of People That Can Be Caught in Tag?
The best approach is a greedy two‑pointers strategy. Maintain two pointers for the positions of players marked 1 ("it") and 0. If the distance between them is within k, count a catch and move both pointers; otherwise move the pointer that is too far behind. This processes the array in O(n) time with O(1) extra space.
Is Maximum Number of People That Can Be Caught in Tag asked at Google/Amazon/Meta?
Greedy pairing and two‑pointer problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The exact problem may vary, but the pattern of matching elements within a distance constraint is a common interview theme.
What data structure is used in Maximum Number of People That Can Be Caught in Tag?
The solution mainly uses arrays and pointer indices. The greedy algorithm scans the array and moves two pointers to pair valid players, so no complex data structures are required beyond basic array traversal.
What is the time complexity of Maximum Number of People That Can Be Caught in Tag?
The optimal greedy solution runs in O(n) time because each pointer moves through the array at most once. Space complexity is O(1) since the algorithm only tracks indices and counters without additional data structures.

Ready to solve this problem?

Practice Maximum Number of People That Can Be Caught in Tag with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Number of Food Buckets to Feed the Hamsters