Maximum Number of People That Can Be Caught in Tag

Maximum Number of People That Can Be Caught in Tag - Problem

Array Greedy Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: team = [0,1,0,1,0], dist = 1

› Output: 2

💡 Note: Guard at position 1 can catch person at position 0 or 2. Guard at position 3 can catch person at position 2 or 4. Using greedy strategy: guard 1 catches position 2, guard 3 catches position 4. Total: 2 catches.

Example 2 — Overlapping Ranges

$ Input: team = [1,0,0,0,1], dist = 2

› Output: 3

💡 Note: Guard at position 0 can catch positions 1 or 2. Guard at position 4 can catch positions 2 or 3. Guard 0 catches position 2 (rightmost), guard 4 catches position 3, and position 1 remains. Actually, guard 0 should catch position 1, guard 4 catches positions 2,3. Total: 3 catches.

Example 3 — Single Guard

$ Input: team = [1,0,0], dist = 1

› Output: 1

💡 Note: Only one guard at position 0. Can catch person at position 1 within range [0,1]. Total: 1 catch.

Constraints

1 ≤ team.length ≤ 10⁵
team[i] is either 0 or 1
1 ≤ dist ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array with guards (1) and people (0), plus distance range

Process

Each guard catches one person within their distance range

Output

Maximum total number of people that can be caught

Key Takeaway

🎯 Key Insight: Greedy assignment (rightmost first) prevents conflicts and maximizes total catches

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use a greedy approach where each guard catches the rightmost available person in their range. This maximizes the total number of catches. Best approach is Greedy Assignment with Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Assignment	O(n²)	O(n)	Process guards left to right, each catches the rightmost available person in range
Brute Force - Try All Assignments	O(2^n)	O(n)	Try all possible ways to assign each guard to catch someone

Greedy Assignment — Algorithm Steps

Find all guards (people with value 1)
Sort guards by position
For each guard, find rightmost uncaught person in range
Mark person as caught and increment counter

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Left to Right

Visit each guard from left to right

Catch Rightmost

Each guard catches rightmost available person in range

Mark Caught

Mark person as caught to avoid double-counting

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* team, int n, int dist) {
    int* caught = (int*)calloc(n, sizeof(int));
    int catches = 0;
    
    for (int i = 0; i < n; i++) {
        if (team[i] == 1) {
            int start = (i - dist < 0) ? 0 : i - dist;
            int end = (i + dist >= n) ? n - 1 : i + dist;
            
            for (int j = end; j >= start; j--) {
                if (team[j] == 0 && !caught[j]) {
                    caught[j] = 1;
                    catches++;
                    break;
                }
            }
        }
    }
    
    free(caught);
    return catches;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int team[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        team[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int dist;
    scanf("%d", &dist);
    
    printf("%d\n", solution(team, n, dist));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each guard, we scan their range to find the rightmost available person

⚠ Quadratic Growth

Space Complexity

O(n)

Array to track which people have been caught

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Assignment — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler