MediumNo. 1989LeetCode Premium
Maximum Number of People That Can Be Caught in Tag — LeetCode 1989 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Array
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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".
Example
- Input
- team = [0,1,0,1,0], dist = 3
- Output
- 2
- Explanation
- The person who is "it" at index 1 can catch people in the range [i-dist, i+dist] = [1-3, 1+3] = [-2, 4].
Python solution
class Solution:
def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:
ans = j = 0
n = len(team)
for i, x in enumerate(team):
if x:
while j < n and (team[j] or i - j > dist):
j += 1
if j < n and abs(i - j) <= dist:
ans += 1
j += 1
return ansComplexity
- Time
- O(n)where n is the length of the array team
- Space · auxiliary
- O(1)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1989. Maximum Number of People That Can Be Caught in Tag is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1996 | The Number of Weak Characters in the Game | Medium |
| 0011 | Container With Most Water | Medium |
| 0134 | Gas Station | Medium |
| 0135 | Candy | Hard |
| 0179 | Largest Number | Medium |
| 0324 | Wiggle Sort II | Medium |
Frequently asked questions
- How hard is LeetCode 1989. Maximum Number of People That Can Be Caught in Tag?
LeetCode 1989. Maximum Number of People That Can Be Caught in Tag is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1989. Maximum Number of People That Can Be Caught in Tag?
The Python solution on this page runs in O(n), where n is the length of the array \textit{team}.
- What is the space complexity of LeetCode 1989. Maximum Number of People That Can Be Caught in Tag?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1989. Maximum Number of People That Can Be Caught in Tag cover?
LeetCode 1989. Maximum Number of People That Can Be Caught in Tag is tagged Greedy and Array on LeetCode.
- Is LeetCode 1989. Maximum Number of People That Can Be Caught in Tag a premium problem?
Yes. LeetCode 1989. Maximum Number of People That Can Be Caught in Tag is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.