1989. Maximum Number of People That Can Be Caught in Tag 🔒

Description

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

Solutions

Solution 1: Two Pointers

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 \(\textit{team}[j]=1\) or \(i - j \gt \textit{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 \(\textit{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 \(\textit{team}\). The space complexity is \(O(1)\).

Python3JavaC++Go

class Solution:
    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:
        ans = j = 0
        n = len(team)
        for i, x in enumerate(team):
            if x:
                while j < n and (team[j] or i - j > dist):
                    j += 1
                if j < n and abs(i - j) <= dist:
                    ans += 1
                    j += 1
        return ans

class Solution {
    public int catchMaximumAmountofPeople(int[] team, int dist) {
        int ans = 0;
        int n = team.length;
        for (int i = 0, j = 0; i < n; ++i) {
            if (team[i] == 1) {
                while (j < n && (team[j] == 1 || i - j > dist)) {
                    ++j;
                }
                if (j < n && Math.abs(i - j) <= dist) {
                    ++ans;
                    ++j;
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int catchMaximumAmountofPeople(vector<int>& team, int dist) {
        int ans = 0;
        int n = team.size();
        for (int i = 0, j = 0; i < n; ++i) {
            if (team[i]) {
                while (j < n && (team[j] || i - j > dist)) {
                    ++j;
                }
                if (j < n && abs(i - j) <= dist) {
                    ++ans;
                    ++j;
                }
            }
        }
        return ans;
    }
};

func catchMaximumAmountofPeople(team []int, dist int) (ans int) {
    n := len(team)
    for i, j := 0, 0; i < n; i++ {
        if team[i] == 1 {
            for j < n && (team[j] == 1 || i-j > dist) {
                j++
            }
            if j < n && abs(i-j) <= dist {
                ans++
                j++
            }
        }
    }
    return
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Comments