We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of People That Can Be Caught in Tag

Number: 1979

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an array "team" where 0 represents a person who is not “it” and 1 represents a person who is “it”, and an integer "dist", each person who is “it” can catch at most one person who is not “it” provided that the target’s index is within the range [i - dist, i + dist]. Return the maximum number of people that can be caught.

Key Insights

  • Separate the indices of taggers (1’s) and non-taggers (0’s).
  • Sorting helps, although the input order already corresponds to indices.
  • Use a two-pointer greedy algorithm to pair each tagger with a valid non-tagger in range.
  • Increment the pointer for tagger and non-tagger whenever a match is found.
  • If the current non-tagger is too far left (before tagger minus dist), move to the next non-tagger.
  • If the current non-tagger is too far right (beyond tagger plus dist), move to the next tagger.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the team array. Space Complexity: O(n), due to storing separate lists for indices of taggers and non-taggers.

Solution

The approach is to traverse through the list with two pointers:

  1. First, create two lists: one for the indices where team[i] is 1 (taggers) and one for where team[i] is 0 (non-taggers).
  2. Initialize two pointers, one for taggers and one for non-taggers.
  3. For each tagger, check if the corresponding non-tagger is in the valid range [tagger - dist, tagger + dist].
  4. If the non-tagger’s index is too small (less than tagger - dist), move the non-tagger pointer.
  5. If the non-tagger’s index is too large (greater than tagger + dist), move the tagger pointer.
  6. If the candidate is in range, count the successful tagging and move both pointers. This greedy approach ensures that each tagger catches at most one non-tagger and each non-tagger is caught only once.

Data structures used include arrays (or lists) for storing indices and two pointers for iteration. This greedy matching method is efficient and straightforward.

Code Solutions

# Python solution for Maximum Number of People That Can Be Caught in Tag
def max_catches(team, dist):
    # Collect indices for non-taggers (0) and taggers (1)
    non_taggers = [i for i, person in enumerate(team) if person == 0]
    taggers = [i for i, person in enumerate(team) if person == 1]
    
    caught = 0  # Count of caught people
    i, j = 0, 0  # Initialize pointers for non_taggers and taggers
    
    # Use two-pointer technique to match each tagger with a non-tagger in range
    while i < len(non_taggers) and j < len(taggers):
        # Calculate valid range for current tagger at taggers[j]
        left_bound = taggers[j] - dist
        right_bound = taggers[j] + dist
        
        # If current non-tagger is too far left, move to the next non-tagger
        if non_taggers[i] < left_bound:
            i += 1
        # If current non-tagger is within range, count the catch and move both pointers
        elif non_taggers[i] <= right_bound:
            caught += 1
            i += 1
            j += 1
        # Else, the non-tagger is too far right for this tagger; move to the next tagger
        else:
            j += 1
            
    return caught

# Example usage:
print(max_catches([0, 1, 0, 1, 0], 3))  # Expected output: 2
← Back to All Questions