1989. Maximum Number of People That Can Be Caught in Tag
Problem Description
In the game of tag described, we're given an array representing two types of players: those who are "it" (represented as 1
) and those who are not "it" (represented as 0
). Each player who is "it" has a specific reach (dist
) which defines the range (inclusive) from their index position within which they can tag a player that is not "it". The goal is to calculate the maximum number of people who are not "it" that can be tagged by those who are "it".
The main challenge is to maximize the number of tags while considering the positions and the reach of the players who are "it". It's essentially a problem of finding the maximum pairing between the players who are "it" and those who are not, within the distance constraints set by dist
.
Intuition
To arrive at the solution, consider that we must optimize the pairing between players who are "it" with those who are not. We can iterate through the team
array, keeping track of two pointers: one for the current player who is "it" (i
) and one for the potential player to catch (j
).
As soon as we encounter a player who is "it", we look to find the nearest player who is not "it" within the legal range of dist
. If such a player exists, we increment our answer ans
, as this represents a successful tag, and move the j
pointer forward to look for the next available player.
This approach naturally leads to a greedy solution, where we prioritize tagging the closest player who is not "it" for each "it" player, because this leaves the possibility open for more distant "it" players to tag those further away. We keep iterating until we either run out of "it" players or we exhaust checking all players who are not "it".
The solution code uses a single loop passing through the whole team, which ensures that the time complexity is linear with respect to the size of the team
array.
Learn more about Greedy patterns.
Solution Approach
The implementation of the solution employs a single pass algorithm with a two-pointer technique, where one pointer (denoted as i
) goes through the team
array, and the other pointer (j
) is used to find the nearest person to be caught.
Here's a step-by-step breakdown of the algorithm:
- Initialize two variables:
ans
to accumulate the number of successful tags, andj
to serve as the pointer for finding someone to catch. - Loop through the
team
array with the indexi
, representing the current person checking for potential tags. - When a person who is "it" (
team[i] == 1
) is encountered, start or continue the inner search with pointerj
. - The inner loop increases the
j
pointer until it finds a person who is not "it" (team[j] == 0
) and is within the catching range (i - j <= dist
). - Once a person to catch is found, increase the answer counter
ans
, and incrementj
to avoid catching the same person more than once. - Repeat this process for each person who is "it" in the
team
array. - If
j
reaches the end of the array (j >= n
), break out of the inner loop since there are no more people left to catch. - Continue until all "it" persons have been processed or no one left to catch.
In terms of data structures, only the original input array team
is used, and no additional space is needed, making this an in-place algorithm with O(1) space complexity.
The time complexity is O(n), where n is the length of the team
array, as each element in the team
is visited up to twice – once by the i
pointer and once by the j
pointer. However, j
does not reset after each iteration; it moves continuously forward.
The given implementation successfully captures the greedy nature of the problem, where each "it" person attempts to catch the nearest possible "not it" person in order to maximize the overall number of tags.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach. Suppose we have the following setup for the game of tag:
- Team array:
team = [0, 1, 0, 0, 1, 0]
- Reach distance:
dist = 2
Our goal here is to maximize the number of people who are not "it" (represented by 0
) that can be tagged by the players who are "it" (represented by 1
).
Let's walk through the algorithm:
- We start with
ans = 0
andj = 0
, whereans
will hold the number of successful tags andj
is our pointer to look for the next player to catch. - Begin iterating through the
team
array (i = 0). Sinceteam[0]
is not "it", we do nothing and continue. - Move to
team[1]
(i = 1). Sinceteam[1]
is "it", we begin looking for the nearest player to catch usingj
. - Increase
j
untilj
reaches 2, satisfying the conditionteam[j] == 0
andi - j <= dist
. We successfully tag the player atj = 2
and incrementans
to 1. - We continue to iterate with
i
now at 2. But sinceteam[2]
is already tagged, we move forward. - At
team[3]
(i = 3), nothing happens since it's not "it". - At
team[4]
(i = 4), we find another "it" player. We start from the current position ofj = 3
. - Since the player at
j = 3
is within reach (i - j <= dist
), we tag them as well, incrementj
to 4, and incrementans
to 2. - Moving to
team[5]
(i = 5), we noticej
is at the end of the array, so no more players can be tagged.
At the end of this walkthrough, ans = 2
, indicating two players were successfully tagged by players who were "it". This reflects a maximized number of tags based on the "greedy" method of tagging the nearest untagged player within reach for each "it" player.
Solution Implementation
1from typing import List
2
3class Solution:
4 def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:
5 # Initialize count of pairs and the index for the team member to be paired with.
6 maximum_pairs = 0
7 team_member_index = 0
8
9 # Get the number of people on the team.
10 number_of_people = len(team)
11
12 # Iterate through members of the team.
13 for i, current_member in enumerate(team):
14 # Check if the current member is ready to catch (indicated by 1).
15 if current_member:
16 # Move the team_member_index forward to find the next ready catcher within the allowed distance.
17 while team_member_index < number_of_people and (team[team_member_index] or i - team_member_index > dist):
18 team_member_index += 1
19
20 # When a valid team member is found within the distance 'dist',
21 # increase the result and move team_member_index forward to pair this catcher.
22 if team_member_index < number_of_people and abs(i - team_member_index) <= dist:
23 maximum_pairs += 1
24 team_member_index += 1
25
26 # Return the maximum number of pairs of people.
27 return maximum_pairs
28
1class Solution {
2 public int catchMaximumAmountOfPeople(int[] team, int dist) {
3 int maxCatches = 0; // This variable stores the maximum number of people that can be caught
4 int teamLength = team.length; // The length of the team array
5
6 // Two pointers, i for catcher's position and j for nearest catchable runner
7 for (int i = 0, j = 0; i < teamLength; ++i) {
8 // Check if current position has a catcher
9 if (team[i] == 1) {
10 // Move j to the next catchable runner within the distance
11 while (j < teamLength && (team[j] == 1 || i - j > dist)) {
12 ++j;
13 }
14 // If j is a valid runner, increment the catch count and move j to next position
15 if (j < teamLength && Math.abs(i - j) <= dist) {
16 maxCatches++; // Increase number of people caught
17 j++; // Move j to the next position
18 }
19 }
20 }
21 // Return the computed maximum number of catches
22 return maxCatches;
23 }
24}
25
1#include <vector>
2#include <cmath>
3
4class Solution {
5public:
6 // Function to calculate the maximum number of people that can be caught
7 int catchMaximumAmountOfPeople(vector<int>& team, int dist) {
8 // Initialize the count of caught people as zero
9 int countCaught = 0;
10 // Get the total number of people
11 const int numPeople = team.size();
12 // Two-pointer method variables: i for catcher, j for catchee
13 for (int i = 0, j = 0; i < numPeople; ++i) {
14 // Isolate the cases where the current person is a catcher (team[i] == 1)
15 if (team[i] == 1) {
16 // Advance the catchee pointer 'j' to find a catchable person
17 while (j < numPeople && (team[j] == 1 || i - j > dist)) {
18 ++j;
19 }
20 // If j is within bounds and within distance 'dist', a catch is possible
21 if (j < numPeople && std::abs(i - j) <= dist) {
22 ++countCaught; // Increase the count of caught people
23 ++j; // Move the 'j' pointer forward to ensure a person can only be caught once
24 }
25 }
26 }
27 // Return the total count of people caught
28 return countCaught;
29 }
30};
31
1// Function to calculate the maximum number of people that can be caught
2function catchMaximumAmountOfPeople(team: number[], dist: number): number {
3 // Initialize the count of people caught as zero
4 let countCaught: number = 0;
5 // Get the total number of people
6 const numPeople: number = team.length;
7
8 // Two-pointer method: 'i' for catcher, 'j' for the person being caught
9 let i: number = 0, j: number = 0;
10 while (i < numPeople) {
11 // Isolate the case where the current person is a catcher (team[i] === 1)
12 if (team[i] === 1) {
13 // Advance the 'j' pointer to find a person who can be caught
14 while (j < numPeople && (team[j] === 1 || Math.abs(i - j) > dist)) {
15 j++;
16 }
17 // If 'j' is within bounds and within the distance 'dist', a catch is possible
18 if (j < numPeople && Math.abs(i - j) <= dist) {
19 countCaught++; // Increase the count of people caught
20 j++; // Move the 'j' pointer forward to ensure a person can only be caught once
21 }
22 }
23 i++; // Move to the next potential catcher
24 }
25
26 // Return the total count of people caught
27 return countCaught;
28}
29
Time and Space Complexity
The given Python code is designed to count the maximum number of people a team can catch within a certain distance dist
. The algorithm uses a greedy two-pointer approach.
Time Complexity
The time complexity of the code is O(n)
, where n
is the length of the team
list. This is because:
- The for-loop iterates through the list once, which contributes
O(n)
. - Inside the loop, the while-loop moves the second pointer
j
forward until it finds a valid person to catch or reaches the end of the list. Each element is visited by thej
pointer at most once throughout the entire execution of the algorithm. Therefore, the total number of operations contributed by the inner while-loop across all iterations of the for-loop is alsoO(n)
.
Hence, the combined time complexity remains O(n)
since both the outer for-loop and the cumulative operations of the inner while-loop are linear with respect to the size of the input list.
Space Complexity
The space complexity of the code is O(1)
.
This is because the algorithm uses a constant amount of extra space for variables ans
, j
, n
, and i
. The space used does not depend on the input size and remains constant even as the input list team
grows in length.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first