Chasers and Runners

Medium

Kids are playing tag standing in a single line. The array players lists them in order: 1 is a chaser and 0 is a runner. You are also given an integer reach. A chaser at position i can catch one runner at a position j with |i - j| ≤ reach. Each chaser catches at most one player, and each runner can be caught only once. Return the largest number of runners the chasers can catch.

Example 1

players=[1, 0, 0, 1, 0, 1], reach=1 → 3

Chaser 0 catches player 1, chaser 3 catches player 2 and chaser 5 catches player 4. All three runners are caught.

Example 2

players=[0, 0, 1, 1], reach=1 → 1

Chaser 2 can catch player 1. The closest runner to chaser 3 is two positions away, beyond reach.

Example 3

players=[1, 1], reach=2 → 0

There are no runners, so nobody can be caught.

Constraints

1 ≤ len(players) ≤ 10⁵
players[i] is 0 or 1
1 ≤ reach ≤ len(players)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array

Similar problems

Two Boards Holding Water Medium Fewest Jumps to the End Medium Reach the Last Cell Medium As Many Trades as You Like Medium Where to Start the Lap Medium

Input

players=[1, 0, 0, 1, 0, 1], reach=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 118 tests on the server, hidden ones included.