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

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

✓ Brute Force - Try All Assignments

⏱️ Time: O(2^n) Space: O(n)

For each person who is 'it', try assigning them to catch each possible person in their range. Use backtracking to explore all combinations and find the maximum.

Greedy Assignment

⏱️ Time: O(n²) Space: O(n)

Iterate through people who are 'it' from left to right. For each guard, assign them to catch the rightmost uncaught person within their range. This greedy strategy maximizes the total number of catches.

Brute Force - Try All Assignments — Algorithm Steps

Find all people who are 'it'
For each 'it' person, try catching each person in range
Use backtracking to avoid double-catching
Return maximum catches found

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Guards

Identify all positions with value 1 (guards)

Try Combinations

For each guard, try catching each person in range

Backtrack

Use recursion to explore all valid combinations

Code -

solution.c — C

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

static int itPeople[1000];
static int caught[1000];

int backtrack(int guardIdx, int itCount, int* team, int n, int dist) {
    if (guardIdx == itCount) return 0;
    
    int maxCatches = backtrack(guardIdx + 1, itCount, team, n, dist);
    
    int itPos = itPeople[guardIdx];
    int start = (itPos - dist < 0) ? 0 : itPos - dist;
    int end = (itPos + dist >= n) ? n - 1 : itPos + dist;
    
    for (int target = start; target <= end; target++) {
        if (team[target] == 0 && !caught[target]) {
            caught[target] = 1;
            int result = 1 + backtrack(guardIdx + 1, itCount, team, n, dist);
            if (result > maxCatches) maxCatches = result;
            caught[target] = 0;
        }
    }
    
    return maxCatches;
}

int solution(int* team, int n, int dist) {
    int itCount = 0;
    
    for (int i = 0; i < n; i++) {
        if (team[i] == 1) itPeople[itCount++] = i;
        caught[i] = 0;
    }
    
    return backtrack(0, itCount, team, n, dist);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    static int team[1000];
    int n = 0;
    
    char* p = line;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        team[n++] = (int)strtol(p, &p, 10);
    }
    
    int dist;
    scanf("%d", &dist);
    
    printf("%d\n", solution(team, n, dist));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each 'it' person has multiple choices, leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and tracking caught people

⚡ 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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Assignments — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler