Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1989.html

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

Level

Medium

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

Solution

Use a greedy approach. For each element 1, find the leftmost element 0 that is within distance dist of the element 1, and the element 0 is caught by the 1. Once an element 0 is caught by an element 1, it can no longer be caught again, so move on to the next element 0. If an element 1 cannot catch any element 0, then move on to the next element 1. Finally, return the number of elements 1 that can catch at least one element 0 each, which is the maximum number of people that can be caught in tag.

  • class Solution {
    public int catchMaximumAmountofPeople(int[] team, int dist) {
        int length = team.length;
        int zero = 0, one = 0;
        while (zero < length && team[zero] != 0)
            zero++;
        while (one < length && team[one] != 1)
            one++;
        int count = 0;
        while (zero < length && one < length) {
            while (one - zero > dist)
                zero++;
            int maxIndex = Math.min(one + dist, length - 1);
            while (zero <= maxIndex && team[zero] != 0)
                zero++;
            if (zero <= maxIndex) {
                count++;
                zero++;
            }
            one++;
            while (one < length && team[one] != 1)
                one++;
        }
        return count;
    }
}

############

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;
    }
};

  • 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


  • 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
}

All Problems

All Solutions