Problem Description

You're playing a tag game where players are divided into two groups: those who are "it" (represented by 1) and those who are not "it" (represented by 0). The players who are "it" try to catch as many players who are not "it" as possible.

Given a 0-indexed integer array team containing only 0s and 1s, and an integer dist:

• 0 represents a player who is not "it"
• 1 represents a player who is "it"
• A player who is "it" at position i can catch exactly one player who is not "it" within the range [i - dist, i + dist] (inclusive)

Each player who is "it" can catch at most one player, and each player who is not "it" can be caught by at most one player.

Your task is to find the maximum number of players that can be caught.

For example, if team = [0, 1, 0, 1, 0] and dist = 2:

• The player at index 1 (who is "it") can catch players at indices 0, 2, or 3 (within range [1-2, 1+2] = [-1, 3])
• The player at index 3 (who is "it") can catch players at indices 1, 2, 4, or 5 (within range [3-2, 3+2] = [1, 5])
• The optimal strategy would be for the player at index 1 to catch the player at index 0, and the player at index 3 to catch the player at index 2 or 4, resulting in 2 catches total.

Intuition

The key insight is that we want to maximize the total number of catches, and each "it" player should catch someone if possible. Since we're traversing from left to right, a greedy approach works well here.

Think about it this way: when we encounter an "it" player at position i, we want to catch the leftmost available non-"it" player within range. Why the leftmost? Because if we skip catching someone on the left and try to catch someone on the right instead, we might be blocking a future "it" player from making a catch. The leftmost uncaught player within our range is the best choice because:

1. We're not "saving" them for anyone else - any "it" player to our left who could have caught them would have already done so
2. By catching the leftmost available player, we leave more options open for "it" players to our right

This naturally leads to a two-pointer approach:

• One pointer i iterates through the array looking for "it" players
• Another pointer j keeps track of the next potential non-"it" player to be caught

When we find an "it" player at position i, we move j forward to find the first uncaught non-"it" player within the range [i - dist, i + dist]. Since j only moves forward and never backward, we ensure that each non-"it" player is caught at most once, and we process everything in a single pass.

The beauty of this approach is that both pointers only move forward, giving us an efficient O(n) solution. We don't need to look backward because any viable catches to the left would have already been made by previous "it" players.

Learn more about Greedy patterns.

Solution Approach

We implement a two-pointer greedy algorithm to solve this problem efficiently.

Algorithm Steps:

1. Initialize variables:

   • ans = 0 to count the total number of catches
   • j = 0 as a pointer to track potential non-"it" players to be caught
   • n = len(team) to store the array length

2. Iterate through the array with pointer i:

   • For each position i, check if team[i] == 1 (player is "it")

3. When we find an "it" player at position i:

   • Move pointer j forward using a while loop to find the first viable catch:

     while j < n and (team[j] or i - j > dist):
         j += 1

     This loop continues while:
     • j < n: We haven't reached the end of the array
     • team[j] == 1: The current player at j is also "it" (can't be caught)
     • i - j > dist: The player at j is too far to the left (outside range)

4. Check if we can make a catch:

   • After the while loop, check if j < n and abs(i - j) <= dist
   • If true, we found a valid non-"it" player within range:
     • Increment ans by 1 (we made a catch)
     • Increment j by 1 (mark this player as caught by moving past them)

5. Continue the process for all "it" players in the array

Why this works:

• The pointer j maintains the invariant that all non-"it" players before position j have either been caught or are out of range for the current "it" player
• Since j never moves backward, each non-"it" player is considered for catching at most once
• The greedy choice of catching the leftmost available player ensures we don't unnecessarily block future catches
• Time complexity is O(n) as both pointers traverse the array at most once
• Space complexity is O(1) as we only use a constant amount of extra space

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example: team = [0, 1, 0, 1, 0] and dist = 2

Initial Setup:

• ans = 0 (no catches yet)
• j = 0 (starting position for finding non-"it" players)
• n = 5 (array length)

Step-by-step execution:

i = 0: team[0] = 0 (not "it"), skip to next position

i = 1: team[1] = 1 (player is "it")

• Start with j = 0
• Check while loop condition: j < 5 ✓ and team[0] = 0 (not "it") and i - j = 1 - 0 = 1 ≤ 2 ✓
• While loop doesn't execute (conditions not met for continuing)
• Check if catch is possible: j = 0 < 5 ✓ and abs(1 - 0) = 1 ≤ 2 ✓
• Make the catch! ans = 1, move j to 1

i = 2: team[2] = 0 (not "it"), skip to next position

i = 3: team[3] = 1 (player is "it")

• Current j = 1
• Check while loop:
  • First iteration: j = 1 < 5 ✓ and team[1] = 1 (is "it"), so increment j to 2
  • Second iteration: j = 2 < 5 ✓ and team[2] = 0 (not "it") and i - j = 3 - 2 = 1 ≤ 2 ✓
  • While loop stops
• Check if catch is possible: j = 2 < 5 ✓ and abs(3 - 2) = 1 ≤ 2 ✓
• Make the catch! ans = 2, move j to 3

i = 4: team[4] = 0 (not "it"), skip to next position

Final Result: ans = 2

The player at index 1 caught the player at index 0, and the player at index 3 caught the player at index 2. This is the maximum number of catches possible.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array team.

The algorithm uses two pointers i and j to traverse the array. The outer loop iterates through each element in the team array exactly once using the enumeration with index i. The inner while loop moves pointer j forward, but crucially, j only moves forward and never resets or moves backward. Since j starts at 0 and can at most reach n-1, the total number of operations for the inner while loop across all iterations of the outer loop is bounded by n. Therefore, even though there's a nested loop structure, each element is visited at most twice (once by i and once by j), resulting in a linear time complexity of O(n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space. The variables ans, j, n, i, and x are all scalar values that don't depend on the input size. No additional data structures like arrays, lists, or hash maps are created. The space used remains constant regardless of the size of the input array, hence the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Resetting the Person Pointer

The Problem: A common mistake is resetting the person_index pointer for each catcher, thinking that each catcher should independently search from the beginning of their range:

# INCORRECT approach
for catcher_index, is_catcher in enumerate(team):
    if is_catcher:
        # Wrong: Starting fresh for each catcher
        person_index = max(0, catcher_index - dist)  
        while person_index <= min(team_length - 1, catcher_index + dist):
            if team[person_index] == 0:
                caught_count += 1
                team[person_index] = -1  # Mark as caught
                break
            person_index += 1

Why It's Wrong:

• This approach has O(n * dist) time complexity instead of O(n)
• It doesn't maintain the optimization that once a person is considered and passed over, they shouldn't be reconsidered

The Solution: Keep the person_index persistent across iterations. Once we've moved past a person (either caught or skipped), we never need to consider them again for future catchers.

Pitfall 2: Not Handling the Bidirectional Range Correctly

The Problem: Some might forget that catchers can catch people both to their left AND right, leading to code that only checks one direction:

# INCORRECT: Only checking to the right
for catcher_index, is_catcher in enumerate(team):
    if is_catcher:
        for j in range(catcher_index + 1, min(team_length, catcher_index + dist + 1)):
            if team[j] == 0:
                caught_count += 1
                team[j] = -1
                break

Why It's Wrong:

• Misses potential catches to the left of the catcher
• Results in suboptimal catch count

The Solution: The correct approach uses the condition abs(catcher_index - person_index) <= dist to ensure both directions are considered. The while loop advances person_index to skip only those positions that are definitively out of range to the left.

Pitfall 3: Modifying the Input Array

The Problem: Attempting to mark caught players by modifying the original array:

# INCORRECT: Modifying the input
if person_index < team_length and abs(catcher_index - person_index) <= dist:
    caught_count += 1
    team[person_index] = -1  # Wrong: Modifying input array
    person_index += 1

Why It's Wrong:

• Modifies the input data which may be needed elsewhere
• The algorithm doesn't actually need to modify the array since the person_index pointer already tracks which players have been considered
• Can cause issues if the same array is used for multiple test cases

The Solution: Simply increment person_index without modifying the array. The pointer advancement naturally ensures each person can only be caught once.