LeetCode 1989 - Maximum Number of People That Can Be Caught in Tag

The problem describes a line of people represented by a binary array team, where each index corresponds to a person. A value of 1 indicates a person who is “it”, and a value of 0 indicates a person who is not “it”.

leetcodemediumarraytwo-pointersgreedy

LeetCode Problem 1989

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy

Solution

Problem Understanding

The problem describes a line of people represented by a binary array team, where each index corresponds to a person. A value of 1 indicates a person who is “it”, and a value of 0 indicates a person who is not “it”. Each “it” person can catch at most one non-“it” person, and only if that target lies within a symmetric distance window [i - dist, i + dist].

The goal is to maximize the total number of non-“it” people caught, given that each “it” person can only catch one target and each non-“it” person can be caught at most once. This naturally introduces a bipartite matching-like constraint, but the structure is linear, which allows a greedy two-pointer strategy.

The input is an array of size up to 10^5, so an O(n^2) solution is too slow. The integer dist defines a local window of interaction, meaning each 1 only “sees” a bounded range of indices.

Edge cases include situations where there are no 1s or no 0s, cases where all 0s are outside all valid windows, and cases where multiple 1s compete for the same 0, requiring careful greedy assignment to avoid suboptimal early matches.

Approaches

The brute-force idea tries every possible pairing: for each 1, scan its valid range and pick an uncaught 0. This works logically because it respects constraints, but it is inefficient because each of the n positions may scan up to 2 * dist or even n elements, leading to quadratic behavior in worst case.

The key insight for optimization is that the problem is fundamentally about matching sorted positions under interval constraints. If we extract indices of all 0s and all 1s, we can greedily match them using two pointers, always assigning the earliest possible valid 0 to each 1. This ensures no future assignment is blocked unnecessarily, which is the standard greedy optimality principle for interval matching problems.

Approach Time Complexity Space Complexity Notes
Brute Force O(n · dist) to O(n²) O(1) extra Try every 1 against all reachable 0s
Optimal Greedy Two Pointers O(n) O(n) Match sorted indices of 1s and 0s greedily

Algorithm Walkthrough

The optimal solution works by separating the problem into two sorted sequences: one containing indices of all people who are “it” and one containing indices of all people who are not “it”. Once we have these two lists, we match them greedily under validity constraints.

  1. First, we scan the team array and collect two lists: ones, which stores indices of all positions with value 1, and zeros, which stores indices of all positions with value 0. This transformation simplifies the problem into matching two sorted integer arrays.
  2. We initialize two pointers, i for iterating over ones and j for iterating over zeros. We also maintain a counter result to track successful matches.
  3. For each ones[i], we attempt to find the earliest valid zeros[j] that lies within its catchable range. The validity condition is abs(ones[i] - zeros[j]) <= dist.
  4. If zeros[j] is too far left (i.e., zeros[j] < ones[i] - dist), then it cannot be matched with this or any future ones[i] that is further right, so we increment j.
  5. If zeros[j] is within range, we assign this 0 to the current 1, increment both pointers, and increase the result counter.
  6. If zeros[j] is too far right, we move to the next 1 because the current 0 cannot be matched yet.
  7. We continue until either list is exhausted.

The greedy choice always assigns the leftmost available valid 0 to the current 1, ensuring that we preserve larger flexibility for future matches.

Why it works

The correctness relies on a greedy invariant: at every step, we match the leftmost feasible 0 with the current 1 in sorted order. This prevents “wasting” a close 0 on a later 1 when it could be used earlier, which would otherwise reduce total matches. Because both lists are processed in order, any alternative assignment can be transformed into this greedy solution without reducing the number of matches, establishing optimality.

Python Solution

from typing import List

class Solution:
    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:
        ones = []
        zeros = []

        for i, v in enumerate(team):
            if v == 1:
                ones.append(i)
            else:
                zeros.append(i)

        i = 0
        j = 0
        result = 0

        while i < len(ones) and j < len(zeros):
            if zeros[j] < ones[i] - dist:
                j += 1
            elif zeros[j] > ones[i] + dist:
                i += 1
            else:
                result += 1
                i += 1
                j += 1

        return result

The implementation begins by extracting index lists for both categories. It then uses a two-pointer traversal to greedily match valid pairs. If a 0 is too far left, it is discarded for future consideration. If it is valid, we match it immediately. If it is too far right, we advance the 1 pointer to find a better candidate.

Go Solution

func catchMaximumAmountofPeople(team []int, dist int) int {
    ones := make([]int, 0)
    zeros := make([]int, 0)

    for i, v := range team {
        if v == 1 {
            ones = append(ones, i)
        } else {
            zeros = append(zeros, i)
        }
    }

    i, j := 0, 0
    result := 0

    for i < len(ones) && j < len(zeros) {
        if zeros[j] < ones[i]-dist {
            j++
        } else if zeros[j] > ones[i]+dist {
            i++
        } else {
            result++
            i++
            j++
        }
    }

    return result
}

In Go, slices are used instead of dynamic lists, but the logic remains identical. Integer arithmetic is safe because indices and constraints fit within standard int. No special handling for nil slices is needed since appending to a nil slice is valid in Go.

Worked Examples

Example 1

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

We first extract:

ones = [1, 3], zeros = [0, 2, 4]

We begin matching:

At ones[0] = 1, zeros[0] = 0 is within range [ -2, 4 ], so we match (1, 0).

State:

i = 1, j = 1, result = 1

At ones[1] = 3, zeros[1] = 2 is within range [0, 6], so we match (3, 2).

State:

i = 2, j = 2, result = 2

Final result is 2.

Example 2

Input: team = [1], dist = 1

ones = [0], zeros = []

Since there are no zeros, the loop never runs and result is 0.

Example 3

Input: team = [0], dist = 1

ones = [], zeros = [0]

Since there are no ones, no matching is possible and result is 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index is visited at most once while building lists and during two-pointer traversal
Space O(n) Stores indices of zeros and ones separately

The linear complexity follows from the fact that each pointer only moves forward and never backtracks, ensuring amortized constant-time processing per element.

Test Cases

# provided examples
assert Solution().catchMaximumAmountofPeople([0,1,0,1,0], 3) == 2  # basic matching case
assert Solution().catchMaximumAmountofPeople([1], 1) == 0          # no zeros
assert Solution().catchMaximumAmountofPeople([0], 1) == 0          # no ones

# edge cases
assert Solution().catchMaximumAmountofPeople([0,0,0,1], 0) == 1    # exact position match only
assert Solution().catchMaximumAmountofPeople([1,0,0,0,1], 1) == 2  # multiple matches possible
assert Solution().catchMaximumAmountofPeople([1,1,1,0,0,0], 2) == 3  # excess catchers
assert Solution().catchMaximumAmountofPeople([0,0,1,0,0], 10) == 2  # large dist covers all
Test Why
[0,1,0,1,0], 3 verifies standard overlapping ranges
[1], 1 no targets exist
[0], 1 no catchers exist
[0,0,0,1], 0 strict equality matching
[1,0,0,0,1], 1 multiple optimal assignments
[1,1,1,0,0,0], 2 more catchers than targets
[0,0,1,0,0], 10 full-range accessibility

Edge Cases

One important edge case is when the array contains only zeros or only ones. In both cases, no matching is possible because the bipartite structure is degenerate. The implementation handles this naturally because one of the lists (ones or zeros) will be empty, and the two-pointer loop will never execute.

Another edge case occurs when dist is zero. In this scenario, only exact index alignment is allowed. The algorithm still works correctly because the condition zeros[j] >= ones[i] - dist and zeros[j] <= ones[i] + dist collapses into equality, and only identical indices are matched.

A third edge case is when dist is very large relative to the array size. In this case, every 1 can potentially match any 0, and the algorithm will greedily pair them one-to-one until one list is exhausted. The correctness holds because the greedy strategy ensures maximum cardinality matching in a fully connected bipartite interval graph.