Maximum Matching of Players With Trainers — Solution
Maximum Matching of Players With Trainers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Matching of Players With Trainers is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Two Pointers
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
players[i] is the ability of player i and trainers[j] the training capacity of trainer j.
Player i can be matched with trainer j when players[i] <= trainers[j]. Every player can be matched with at most one trainer, and every trainer with at most one player.
Return the maximum number of matchings.
Example 1
Input: players = [3,1,6], trainers = [2,6,4,1]
Output: 3
Explanation: 1 with 1, 3 with 4, 6 with 6.
Example 2
Input: players = [4,7,9], trainers = [8,2,5,8]
Output: 2
Example 3
Input: players = [1,1,1], trainers = [10]
Output: 1
Constraints
1 <= players.length, trainers.length <= 10^51 <= players[i], trainers[j] <= 10^9
Hints for Maximum Matching of Players With Trainers
Hint 1
The weakest player is the easiest to place; the weakest trainer is the most constrained.
Hint 2
Sort both arrays.
Hint 3
Walk them with two pointers: if the current trainer can take the current player, match them and advance both; otherwise this trainer is too weak for everyone left — skip it.
How to solve Maximum Matching of Players With Trainers
Give each player, from weakest to strongest, the weakest trainer that can still handle them. Two pointers over the sorted arrays implement it in one pass.
Approach
- Sort
playersandtrainersascending. - Set
i = j = matched = 0. - While both pointers are in range: if
players[i] <= trainers[j], match them (matched++,i++,j++); otherwisej++. - Return
matched.
Why it works
A trainer too weak for the current (weakest unmatched) player is too weak for every later player, so skipping it loses nothing. When the trainer fits, pairing it with the weakest player is safe by exchange: in any optimal matching, swapping partners so that the weakest player takes the weakest usable trainer keeps every pair valid, because the stronger trainer it frees is at least as capable.
Complexity
- Time —
O(n log n + m log m) - Space —
O(1) beyond the sorts
Pitfalls
- The condition is
player <= trainer; equality counts as a match. - Advance only the trainer pointer when a trainer is too weak — the player still needs one.
- Matching the strongest player first with the strongest trainer also works; mixing directions does not.
Reference solution
Python
from typing import List
def matchPlayersAndTrainers(players: List[int], trainers: List[int]) -> int:
p, t = sorted(players), sorted(trainers)
i = j = matched = 0
while i < len(p) and j < len(t):
if p[i] <= t[j]:
matched += 1
i += 1
j += 1
return matchedJava
public static int matchPlayersAndTrainers(int[] players, int[] trainers) {
int[] p = players.clone(), t = trainers.clone();
Arrays.sort(p);
Arrays.sort(t);
int i = 0, j = 0, matched = 0;
while (i < p.length && j < t.length) {
if (p[i] <= t[j]) {
matched++;
i++;
}
j++;
}
return matched;
}C++
int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
vector<int> p = players, t = trainers;
sort(p.begin(), p.end());
sort(t.begin(), t.end());
size_t i = 0, j = 0;
int matched = 0;
while (i < p.size() && j < t.size()) {
if (p[i] <= t[j]) {
matched++;
i++;
}
j++;
}
return matched;
}JavaScript
var matchPlayersAndTrainers = function(players, trainers) {
var p = players.slice().sort(function(a, b) { return a - b; });
var t = trainers.slice().sort(function(a, b) { return a - b; });
var i = 0, j = 0, matched = 0;
while (i < p.length && j < t.length) {
if (p[i] <= t[j]) {
matched++;
i++;
}
j++;
}
return matched;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms