Maximize the Number of People That Can Be Caught in Tag

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”. Given an array of 0s and 1s, where 0s are people not “it” and 1s are people who are “it“. 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”. The task is to find maximum number of people that the people who are “it” can catch.

Example:

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 but the answer should be 3.

Input: team = {1}, dist = 1
Output: 0
Explanation: There are no people who are not “it” to catch.

Approach:

1. If we count the number of 1s and 0s in given team as ones and zeros, the answer cannot exceed ones, since each person “it” can catch at most 1 other person.

For example:

• team = [0,1,1,1], dist = 1 -> answer = 1
• team = [1,0,0,1,0,1], dist = 1 -> answer = 3

2. When there are reachable 0s for a person, we want to catch as far left as possible. So as to maximize opportunity for 1s to its rightside.

For example:

• team = [0,1,0,1] dist = 1
• if team[1] catch team[2], team[3] won’t be able to catch any person.
• if team[1] catch team[0], team[3] can catch team[2] [1,0,0,0,1,1] dist = 2
• if team[0] catch team[2], team[4] can only catch team[3], and answer is 2.

3. Apply two pointers. Whenever we meet 1, scan reachable range, following previous position after the 0, for the first 0.

Steps-by-step approach:

• Initialize variables teamSize: Get the size of the team and peopleCaught: Initialize the count of people caught to 0.
• Iterate over the team using a loop.
  • Initialize two iterators: itPerson and nonItPerson.
  • Iterate nonItPerson until it reaches the end of the team.
  • Inside the loop:
    • Check if the person is “it” (team[nonItPerson] == 1).
    • Adjust the iterator itPerson to ensure it doesn’t go beyond the team size and within the catchable range (itPerson = max(itPerson, nonItPerson – dist)).
    • Determine the last person the “it” person can catch (lastCatchablePerson).
    • Try to catch a person within the catchable range using a while loop.
      • If the person is not “it“, catch them and break the loop.
• Return the total number of people caught.

Below is the implementation of the above approach:

#include <bits/stdc++.h>
using namespace std;

int maxPeopleCaught(vector<int>& team, int dist)
{
    // Get the size of the team
    int teamSize = team.size();

    // Initialize the count of people caught to 0
    int peopleCaught = 0;

    // Iterate over the team
    for (int itPerson = 0, nonItPerson = 0;
         nonItPerson < teamSize; nonItPerson++) {

        // If the person is "it"
        if (team[nonItPerson] == 1) {

            // Ensure the "it" person does not go beyond the
            // team size
            itPerson = max(itPerson, nonItPerson - dist);

            // Determine the last person the "it" person can
            // catch
            int lastCatchablePerson
                = min(nonItPerson + dist, teamSize - 1);

            // Try to catch a person
            while (itPerson <= lastCatchablePerson) {

                // If the person is not "it", catch them and
                // break the loop
                if (team[itPerson++] == 0) {
                    peopleCaught++;
                    break;
                }
            }
        }
    }

    // Return the total number of people caught
    return peopleCaught;
}

int main()
{

    // input team and distance
    vector<int> team = { 1, 0, 0, 1, 0, 1, 0, 0, 1 };
    int dist = 2;

    // Call the maxPeopleCaught method with the static input
    int maxCaught = maxPeopleCaught(team, dist);

    // Print the maximum number of people that can be caught
    cout << "The maximum number of people that can be "
            "caught is "
         << maxCaught << "." << endl;

    return 0;
}

The maximum number of people that can be caught is 4.

Time Complexity: O(n)
Auxiliary Space: O(1)