Problem Description

Given two arrays, players and runners, both representing positions along a line, and an integer k representing the maximum distance a player can catch a runner, determine the maximum number of runners that can be caught by the players. Each player can catch at most one runner, and each runner can be caught by at most one player. A player can only catch a runner if their positions differ by at most k (i.e., abs(players[i] - runners[j]) <= k).

The goal is to find the maximum number of runners that can be caught under these constraints.

Thought Process

At first glance, the problem seems to invite a brute-force approach: for every player, check all runners to see if they are within distance k and have not been caught yet. However, this leads to a highly inefficient solution with a time complexity of O(N*M), where N and M are the lengths of the players and runners arrays.

Instead, we can draw an analogy to the "maximum bipartite matching" or "interval matching" problems, where each player is trying to be paired with a runner within a certain range. Since both arrays represent positions, sorting them allows us to efficiently pair players and runners using a two-pointer technique.

The key insight is that by sorting both arrays, we can always try to match the leftmost (smallest position) player with the leftmost available runner within their reach, ensuring no one is skipped unnecessarily.

Solution Approach

To solve the problem efficiently, follow these steps:

1. Sort both the players and runners arrays in ascending order. This allows us to efficiently find the nearest available runner for each player.
2. Initialize two pointers: one for players (i) and one for runners (j).
3. Iterate through both arrays:
   • If abs(players[i] - runners[j]) <= k, we have a match. Increment both i and j, and increment the count of caught runners.
   • If players[i] < runners[j], move the player pointer forward (i++), since the current player is too far left to catch the runner.
   • Otherwise, move the runner pointer forward (j++), since the runner is too far left to be caught by the current player.
4. Continue until either pointer reaches the end of its respective array.
5. Return the count of successful matches.

This approach ensures we never revisit a player or runner, making the solution efficient and optimal.

Example Walkthrough

Suppose players = [1, 4, 5], runners = [2, 3, 6], and k = 1.

1. After sorting (already sorted), players = [1, 4, 5], runners = [2, 3, 6].
2. Step 1: i = 0, j = 0: abs(1 - 2) = 1 ≤ 1, match! Increment both pointers and matches = 1.
3. Step 2: i = 1, j = 1: abs(4 - 3) = 1 ≤ 1, match! Increment both pointers and matches = 2.
4. Step 3: i = 2, j = 2: abs(5 - 6) = 1 ≤ 1, match! Increment both pointers and matches = 3.
5. Both pointers reach the end. The answer is 3 (all runners can be caught).

If, for example, k = 0, then no player could catch any runner unless they are at the exact same position.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(N*M), where N and M are the lengths of players and runners.
• Space Complexity: O(1) (not counting input storage).

• Time Complexity: O(N log N + M log M) due to sorting, plus O(N + M) for the two-pointer pass.
• Space Complexity: O(1) extra space (if sorting in-place), or O(N + M) if making copies for sorting.

The optimized approach is much faster and suitable for large inputs.

Summary

By sorting both arrays and using a two-pointer technique, we efficiently pair up players and runners within the allowed distance, ensuring each is used at most once. This solution is elegant, optimal, and leverages classic algorithmic techniques for matching problems, making it both practical and easy to understand.

Code Implementation

def max_caught(players, runners, k):
    players.sort()
    runners.sort()
    i = j = count = 0
    while i < len(players) and j < len(runners):
        if abs(players[i] - runners[j]) <= k:
            count += 1
            i += 1
            j += 1
        elif players[i] < runners[j]:
            i += 1
        else:
            j += 1
    return count
      

#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

int maxCaught(vector<int>& players, vector<int>& runners, int k) {
    sort(players.begin(), players.end());
    sort(runners.begin(), runners.end());
    int i = 0, j = 0, count = 0;
    while (i < players.size() && j < runners.size()) {
        if (abs(players[i] - runners[j]) <= k) {
            count++;
            i++;
            j++;
        } else if (players[i] < runners[j]) {
            i++;
        } else {
            j++;
        }
    }
    return count;
}
      

import java.util.*;

public class Solution {
    public int maxCaught(int[] players, int[] runners, int k) {
        Arrays.sort(players);
        Arrays.sort(runners);
        int i = 0, j = 0, count = 0;
        while (i < players.length && j < runners.length) {
            if (Math.abs(players[i] - runners[j]) <= k) {
                count++;
                i++;
                j++;
            } else if (players[i] < runners[j]) {
                i++;
            } else {
                j++;
            }
        }
        return count;
    }
}
      

function maxCaught(players, runners, k) {
    players.sort((a, b) => a - b);
    runners.sort((a, b) => a - b);
    let i = 0, j = 0, count = 0;
    while (i < players.length && j < runners.length) {
        if (Math.abs(players[i] - runners[j]) <= k) {
            count++;
            i++;
            j++;
        } else if (players[i] < runners[j]) {
            i++;
        } else {
            j++;
        }
    }
    return count;
}