LeetCode 2410 - Maximum Matching of Players With Trainers

This problem requires us to maximize the number of matchings between players and trainers under the condition that a player's ability cannot exceed the trainer's training capacity. In other words, a player i can only be assigned to trainer j if players[i] <= trainers[j].

leetcodemediumarraytwo-pointersgreedysorting

LeetCode Problem 2410

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

Solution

Problem Understanding

This problem requires us to maximize the number of matchings between players and trainers under the condition that a player's ability cannot exceed the trainer's training capacity. In other words, a player i can only be assigned to trainer j if players[i] <= trainers[j]. Additionally, each player and each trainer can participate in at most one match.

The input consists of two integer arrays: players and trainers. Each array can be large, up to 10^5 elements, and each value can be up to 10^9. This tells us that nested loops checking every possible pairing would be too slow, so we need an approach that scales linearly or near-linearly with sorting.

The output is a single integer representing the maximum number of valid matches possible.

Edge cases to keep in mind include:

  • One array is much longer than the other (e.g., many players but only one trainer).
  • Players or trainers with the same ability or capacity.
  • All players being stronger than all trainers, resulting in zero matches.

Approaches

Brute Force Approach

A naive approach would be to iterate over each player and try to find a trainer that can accommodate them. Once matched, the trainer would be removed from consideration. This approach guarantees correctness but requires checking each player against each trainer, giving O(n*m) time complexity. Given the constraints (n, m <= 10^5), this approach is far too slow.

Optimal Approach

The optimal approach leverages sorting and a two-pointer technique. The key insight is that if we sort both arrays in ascending order, we can match the smallest available player with the smallest available trainer that satisfies the ability condition. This ensures we do not waste stronger trainers on weaker players unnecessarily, maximizing the total number of matches.

The steps are as follows: sort both arrays, initialize two pointers for players and trainers, and iterate through them. If the current player can be matched with the current trainer, increment both pointers and the match count. If the player cannot be matched, move the trainer pointer forward until a suitable trainer is found.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Check each player against all trainers; slow for large input
Optimal O(n log n + m log m) O(1) Sort arrays and use two pointers for linear scan

Algorithm Walkthrough

  1. Sort the players array in ascending order.

  2. Sort the trainers array in ascending order.

  3. Initialize two pointers i = 0 (for players) and j = 0 (for trainers) and a counter matches = 0.

  4. While both pointers are within array bounds:

  5. Compare players[i] with trainers[j].

  6. If players[i] <= trainers[j], it means this player can be matched. Increment both i and j, and increase matches by 1.

  7. Otherwise, if players[i] > trainers[j], move j forward to find a trainer that can accommodate this player.

  8. Once either pointer reaches the end, return matches.

Why it works: Sorting ensures that we always try to use the least capable trainer who can still accommodate the player. This preserves stronger trainers for stronger players, guaranteeing a maximal matching without skipping potential matches.

Python Solution

from typing import List

class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
        players.sort()
        trainers.sort()
        
        i, j = 0, 0
        matches = 0
        
        while i < len(players) and j < len(trainers):
            if players[i] <= trainers[j]:
                matches += 1
                i += 1
                j += 1
            else:
                j += 1
        
        return matches

The Python implementation follows the algorithm exactly. Sorting ensures the smallest player is matched with the smallest possible trainer, and the two-pointer loop efficiently counts matches without unnecessary checks.

Go Solution

import "sort"

func matchPlayersAndTrainers(players []int, trainers []int) int {
    sort.Ints(players)
    sort.Ints(trainers)
    
    i, j := 0, 0
    matches := 0
    
    for i < len(players) && j < len(trainers) {
        if players[i] <= trainers[j] {
            matches++
            i++
            j++
        } else {
            j++
        }
    }
    
    return matches
}

In Go, the implementation is similar. We use sort.Ints to sort the slices, and integer arithmetic ensures there is no risk of overflow. Empty slices are handled naturally because the loop condition fails immediately.

Worked Examples

Example 1

players = [4,7,9], trainers = [8,2,5,8]

After sorting:

players = [4,7,9], trainers = [2,5,8,8]

Step by step:

i j players[i] trainers[j] Action Matches
0 0 4 2 4>2, skip trainer 0
0 1 4 5 4<=5, match 1
1 2 7 8 7<=8, match 2
2 3 9 8 9>8, skip trainer 2
2 4 9 - end 2

Output: 2

Example 2

players = [1,1,1], trainers = [10]

Sorted arrays:

players = [1,1,1], trainers = [10]

Step by step:

i j players[i] trainers[j] Action Matches
0 0 1 10 1<=10, match 1
1 1 1 - end 1

Output: 1

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + m log m) Sorting both arrays dominates; linear scan is O(n+m)
Space O(1) Only pointers and counters used; in-place sorting assumed

Sorting dominates the runtime, and the two-pointer traversal ensures we do not exceed linear time after sorting.

Test Cases

# Provided examples
assert Solution().matchPlayersAndTrainers([4,7,9], [8,2,5,8]) == 2  # Example 1
assert Solution().matchPlayersAndTrainers([1,1,1], [10]) == 1      # Example 2

# Edge cases
assert Solution().matchPlayersAndTrainers([], []) == 0             # Both empty
assert Solution().matchPlayersAndTrainers([5], []) == 0            # No trainers
assert Solution().matchPlayersAndTrainers([], [5]) == 0            # No players
assert Solution().matchPlayersAndTrainers([10,20], [5,15]) == 1   # Only one match possible
assert Solution().matchPlayersAndTrainers([1,2,3], [1,2,3]) == 3  # Perfect match
assert Solution().matchPlayersAndTrainers([5,5,5], [4,4,4]) == 0  # No matches possible
Test Why
Both empty Checks handling of empty input
No trainers Ensures zero matches if no trainers
No players Ensures zero matches if no players
Only one match possible Tests matching when capacities are mixed
Perfect match Confirms maximum matches when arrays align exactly
No matches possible Tests when all players exceed trainer capacity

Edge Cases

Empty arrays: Both players or trainers can be empty. The algorithm correctly returns 0 because the loop never executes.

All players stronger than trainers: If every player has higher ability than all trainers, the algorithm will iterate through trainers without ever incrementing the match counter. This correctly results in zero matches.

Duplicate abilities and capacities: Multiple players or trainers with the same value are handled naturally. Sorting ensures that each player tries to match with the first available trainer who satisfies the condition, ensuring no duplicates are skipped or double-counted.