Problem Description

You have two groups: players and trainers. Each player has an ability value, and each trainer has a training capacity value.

A player can be matched with a trainer only if the player's ability is less than or equal to the trainer's training capacity. Each player can match with at most one trainer, and each trainer can match with at most one player.

Given two arrays:

• players[i] represents the ability of the i-th player
• trainers[j] represents the training capacity of the j-th trainer

Your task is to find the maximum number of matchings possible between players and trainers while satisfying the matching conditions.

For example, if you have players with abilities [4, 7, 9] and trainers with capacities [8, 2, 5, 8], you could match:

• Player with ability 4 → Trainer with capacity 5
• Player with ability 7 → Trainer with capacity 8
• Player with ability 9 cannot be matched (no trainer with capacity ≥ 9 remaining)

This would give you 2 matchings. Note that once a trainer is matched with a player, that trainer cannot be used again for another player.

Intuition

The key insight is that we want to maximize the number of matchings, and we should avoid "wasting" trainers with high capacity on players with low ability.

Think about it this way: if we have a player with ability 3 and another with ability 8, and we have trainers with capacities 5 and 10, we shouldn't match the player with ability 3 to the trainer with capacity 10. Why? Because that would leave the player with ability 8 unmatched, when we could have matched player 3 with trainer 5, and player 8 with trainer 10.

This naturally leads us to a greedy strategy: match each player with the trainer who has the smallest sufficient capacity. By "sufficient," we mean the trainer's capacity must be at least equal to the player's ability.

To implement this efficiently, we can sort both arrays. After sorting:

• For each player (starting from the weakest), we look for the weakest trainer who can handle them
• Once we find a suitable trainer, we match them and move on to the next player
• If a trainer is too weak for a player, that trainer won't be suitable for any stronger players either, so we can skip that trainer permanently

This two-pointer approach works because:

1. Sorting ensures we always try to use the "cheapest" available resource (trainer with lowest capacity) for each player
2. We never need to look backwards - if a trainer couldn't handle a weaker player, they definitely can't handle a stronger one
3. By processing players from weakest to strongest, we ensure we're not blocking stronger players from getting matched by using up high-capacity trainers unnecessarily

Learn more about Greedy, Two Pointers and Sorting patterns.

Solution Approach

The solution uses a greedy algorithm with two pointers to find the maximum number of matchings.

Step 1: Sort both arrays

players.sort()
trainers.sort()

Sorting allows us to process players and trainers in ascending order of their abilities/capacities.

Step 2: Initialize two pointers

• Pointer j = 0 tracks the current position in the trainers array
• Variable n = len(trainers) stores the total number of trainers
• We'll iterate through players using enumeration with index i

Step 3: Match players with trainers For each player at position i with ability p:

while j < n and trainers[j] < p:
    j += 1

This loop finds the first trainer whose capacity is greater than or equal to the current player's ability. We skip all trainers who are too weak for this player.

Step 4: Check if matching is possible

if j == n:
    return i

If j reaches the end of the trainers array (j == n), it means there are no more trainers available who can handle the current player or any subsequent stronger players. We return i, which represents the number of players successfully matched so far.

Step 5: Move to next trainer

j += 1

If we found a suitable trainer, we match them with the current player and increment j to move to the next trainer (since each trainer can only be matched once).

Step 6: Return total matches

return len(players)

If we successfully iterate through all players without running out of suitable trainers, it means all players have been matched, so we return the total number of players.

Time Complexity: O(n log n + m log m) where n is the number of players and m is the number of trainers, due to sorting both arrays. The matching process itself is O(n + m).

Space Complexity: O(1) if we don't count the space used for sorting (which depends on the sorting algorithm used).

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• players = [9, 4, 7] (abilities)
• trainers = [2, 8, 5, 8] (capacities)

Step 1: Sort both arrays

• players = [4, 7, 9] (sorted)
• trainers = [2, 5, 8, 8] (sorted)

Step 2: Initialize pointers

• j = 0 (pointer for trainers)
• matchings = 0 (count successful matches)

Step 3: Process each player

Player 0 (ability = 4):

• Check trainer at j=0: capacity = 2 < 4 (too weak)
• Move j to 1
• Check trainer at j=1: capacity = 5 ≥ 4 (suitable!)
• Match player 0 with trainer 1
• Increment j to 2
• Matchings: 1

Player 1 (ability = 7):

• Check trainer at j=2: capacity = 8 ≥ 7 (suitable!)
• Match player 1 with trainer 2
• Increment j to 3
• Matchings: 2

Player 2 (ability = 9):

• Check trainer at j=3: capacity = 8 < 9 (too weak)
• Move j to 4
• j = 4 equals array length (no more trainers)
• Cannot match this player
• Return current matchings: 2

Result: Maximum matchings = 2

The key insight demonstrated here is that by processing both sorted arrays with two pointers, we efficiently find the optimal matching without wasting high-capacity trainers on low-ability players. The trainer with capacity 2 was correctly skipped, and the trainers with capacities 5 and 8 were matched with players 4 and 7 respectively, leaving player 9 unmatched since no remaining trainer has sufficient capacity.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × log m + n × log n), where m is the length of the players array and n is the length of the trainers array.

• Sorting the players array takes O(m × log m) time
• Sorting the trainers array takes O(n × log n) time
• The iteration through players with the while loop takes O(m + n) time in the worst case, as each trainer is visited at most once due to the monotonic increment of index j
• The overall time complexity is dominated by the sorting operations: O(m × log m + n × log n)

Space Complexity: O(max(log m, log n))

• The sorting operations use O(log m) space for sorting the players array and O(log n) space for sorting the trainers array (typical space complexity for sorting algorithms like Timsort used in Python)
• No additional data structures are used besides a few variables (j, n, i, p) which take O(1) space
• The overall space complexity is O(max(log m, log n)) due to the sorting operations' recursive call stack

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to increment the trainer pointer after matching

A common mistake is forgetting to increment trainer_index after successfully finding a match. This would cause the same trainer to be matched with multiple players, violating the constraint that each trainer can only match with one player.

Incorrect Code:

for player_index, player_ability in enumerate(players):
    while trainer_index < num_trainers and trainers[trainer_index] < player_ability:
        trainer_index += 1
  
    if trainer_index == num_trainers:
        return player_index
  
    # MISSING: trainer_index += 1

Solution: Always remember to increment trainer_index after a successful match to mark that trainer as "used."

Pitfall 2: Not sorting both arrays

Some might attempt to solve this problem without sorting, thinking they can just iterate and find matches. This greedy approach without sorting will miss optimal matchings.

Example of why sorting is necessary:

• Players: [9, 1]
• Trainers: [10, 1]

Without sorting, you might match player 9 with trainer 10, leaving player 1 unmatched with trainer 1. But if you sort first, you match player 1 with trainer 1, and player 9 with trainer 10, getting 2 matches instead of 1.

Solution: Always sort both arrays before applying the two-pointer technique.

Pitfall 3: Using nested loops instead of two pointers

A naive approach might use nested loops to check every player against every trainer:

Inefficient Code:

matches = 0
used_trainers = set()
for player in players:
    for j, trainer in enumerate(trainers):
        if j not in used_trainers and trainer >= player:
            matches += 1
            used_trainers.add(j)
            break
return matches

This has O(n*m) time complexity and won't pass time limits for large inputs.

Solution: Use the two-pointer technique after sorting, which reduces complexity to O(n log n + m log m).

Pitfall 4: Incorrect boundary check in the while loop

Using <= instead of < in the while loop condition can cause an index out of bounds error:

Incorrect Code:

while trainer_index <= num_trainers and trainers[trainer_index] < player_ability:
    trainer_index += 1

When trainer_index equals num_trainers, accessing trainers[trainer_index] will raise an IndexError.

Solution: Always use trainer_index < num_trainers to ensure valid array access.