2410. Maximum Matching of Players With Trainers
Problem Description
In this LeetCode problem, you are given two 0-indexed integer arrays: players
and trainers
. Each entry in the players
array represents the ability of a particular player, and each entry in the trainers
array represents the training capacity of a particular trainer. A player can be matched with a trainer if the player's ability is less than or equal to the trainer's capacity. It's important to note that each player can only be matched with one trainer, and each trainer can match with only one player. The task is to find the maximum number of such player-trainer pairings where the conditions of matching ability to capacity are met.
Intuition
The intuition behind the solution is straightforward: we want to pair as many players with trainers as we can, prioritizing the pairing of less able players with trainers who have just enough capacity to train them. This ensures that we do not 'waste' a trainer with high capacity on a player with low ability when that trainer could be matched with a more able player instead.
To achieve this, we sort both the players
and trainers
arrays. Sorting helps us easily compare the least able player with the least capable trainer and move up their respective arrays. If a match is found, both the player and the trainer are effectively removed from the potential pool by moving to the next elements in the arrays (incrementing the index). If no match is found, we move up the trainers
array to find the next trainer with a higher capacity that might match the player’s ability.
The result is incrementally built by adding a match whenever we find a capable trainer for a player. We stop when we've either paired all players or run out of trainers. The sum of matches made gives us the maximum number of possible pairings.
Learn more about Greedy, Two Pointers and Sorting patterns.
Solution Approach
The implementation provided uses a simple but effective greedy approach, heavily relying on sorting. The steps involve:
-
Sorting the
players
array in ascending order, which ensures we start with the player with the lowest ability. -
Sorting the
trainers
array in ascending order, which allows us to start with the trainer having the lowest capacity.
The algorithm works with two pointers, one (i
) iterating through the players
array, and the other (j
) through the trainers
array.
Here is the implementation broken down:
-
Initialize a variable
ans
to0
to keep track of the number of matches made. -
Initialize the trainer index pointer
j
to0
. -
Iterate over each player
p
in the sortedplayers
list using a for-loop.-
Within the loop, proceed with an inner while-loop which continues as long as
j
is less than the length oftrainers
and the current trainer's capacitytrainers[j]
is less than the ability of the playerp
. The purpose of this loop is to find the first trainer in the sorted list whose capacity is sufficient to train the player. -
After the while-loop, if
j
is still within the bounds of thetrainers
array, it means a suitable trainer has been found for the playerp
. We incrementans
to count the match and also incrementj
to move to the next trainer.
-
-
Once all players have been considered, return the value of
ans
.
Algorithm and Data Structures:
-
Lists: The main data structure used here are lists (
players
andtrainers
), which are sorted. -
Greedy approach: The algorithm uses a greedy method by matching each player with the "smallest" available trainer that can train them.
-
Two pointers: It uses two pointers to pair players with trainers without revisiting or re-comparing them, thus optimizing the process.
-
Sorting: By sorting the arrays, the solution leverages the property that once a player cannot be paired with a current trainer, they cannot be paired with any trainers before that one in the sorted list either.
Patterns used:
- Sorting and Two-pointers: This is a common pattern for efficiently pairing elements from two different sorted lists.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we have the following players
and trainers
arrays:
players
:[2, 3, 4]
trainers
:[1, 2, 5]
Following the solution approach:
-
We first sort both the
players
andtrainers
arrays:After sorting,
players
:[2, 3, 4]
(already sorted)trainers
:[1, 2, 5]
(already sorted)
-
We initialize
ans
to0
. This variable will keep track of the successful player-trainer matches. -
We also initialize the trainer index pointer
j
to0
.
Now, let's go through each player and try to find a trainer match:
-
Player with ability
2
is the first in theplayers
array.- We check the trainers in order: trainer
1
cannot train the player because the trainer's capacity is too low. - Move to the next trainer (
2
), and we find a match. Trainer2
can train the player with ability2
. - We increment
ans
to1
and move to the next trainer (j
becomes2
).
- We check the trainers in order: trainer
-
Player with ability
3
is the next.- The trainer in position
2
in the sortedtrainers
list has a capacity of5
, which is sufficient. - We match this player with the trainer.
- We increment
ans
to2
, and since there are no more trainers, we move on to the final player.
- The trainer in position
-
Player with ability
4
:- There are no more trainers to compare since we exceeded the length of the
trainers
array.
- There are no more trainers to compare since we exceeded the length of the
At the end of this process, the value of ans
is 2
, which signifies that we were able to match two pairs of players and trainers successfully.
Solution Implementation
1from typing import List # Import List from typing module for type hints
2
3class Solution:
4 def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
5 # Sort the list of players in ascending order
6 players.sort()
7 # Sort the list of trainers in ascending order
8 trainers.sort()
9
10 # Initialize the count of matched players and trainers
11 match_count = 0
12 # Initialize the pointer for trainers list
13 trainer_index = 0
14
15 # Iterate over each player in the sorted list
16 for player in players:
17 # Skip trainers which have less capacity than the current player's strength
18 while trainer_index < len(trainers) and trainers[trainer_index] < player:
19 trainer_index += 1
20
21 # If there is a trainer that can match the current player
22 if trainer_index < len(trainers):
23 # Increment the match count
24 match_count += 1
25 # Move to the next trainer for the next player
26 trainer_index += 1
27
28 # Return the total number of matches
29 return match_count
30
1class Solution {
2 public int matchPlayersAndTrainers(int[] players, int[] trainers) {
3 // Sort the players array in ascending order
4 Arrays.sort(players);
5 // Sort the trainers array in ascending order
6 Arrays.sort(trainers);
7
8 // Initialize the count of matches to 0
9 int matches = 0;
10 // Initialize the index for trainers to 0
11 int trainerIndex = 0;
12
13 // Iterate over each player
14 for (int player : players) {
15 // Increment the trainerIndex until we find a trainer that can match the player
16 while (trainerIndex < trainers.length && trainers[trainerIndex] < player) {
17 trainerIndex++;
18 }
19 // If there is a trainer that can match the player, increment the match count
20 if (trainerIndex < trainers.length) {
21 matches++; // A match is found
22 trainerIndex++; // Move to the next trainer.
23 }
24 }
25 // Return the total count of matches
26 return matches;
27 }
28}
29
1#include <vector>
2#include <algorithm> // Include the necessary header for std::sort
3
4class Solution {
5public:
6 // Function to match players with trainers based on their strength.
7 // Each player can only be matched with a trainer that is equal or greater in strength.
8 int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
9 std::sort(players.begin(), players.end()); // Sort the players in ascending order
10 std::sort(trainers.begin(), trainers.end()); // Sort the trainers in ascending order
11
12 int matches = 0; // Initialize the number of matches to zero
13 int trainersIndex = 0; // Initialize the trainers index to the start of the array
14
15 // Iterate through each player
16 for (int playerStrength : players) {
17 // Find a trainer that can match the current player's strength
18 while (trainersIndex < trainers.size() && trainers[trainersIndex] < playerStrength) {
19 trainersIndex++; // Increment trainers index if the current trainer is weaker than the player
20 }
21
22 // If a suitable trainer is found, make the match
23 if (trainersIndex < trainers.size()) {
24 matches++; // Increment match count
25 trainersIndex++; // Move to the next trainer for the following players
26 }
27 }
28
29 return matches; // Return the total number of matches made
30 }
31};
32
1// Import the necessary module for sorting
2import { sort } from 'some-sorting-module'; // Please replace 'some-sorting-module' with the actual module you would use for sorting
3
4// Function to sort an array in ascending order
5function sortArrayAscending(array: number[]): number[] {
6 return sort(array, (a, b) => a - b);
7}
8
9// Function to match players with trainers based on their strength.
10// Each player can only be matched with a trainer that is equal or greater in strength.
11function matchPlayersAndTrainers(players: number[], trainers: number[]): number {
12 // Sort the players and trainers in ascending order
13 const sortedPlayers: number[] = sortArrayAscending(players);
14 const sortedTrainers: number[] = sortArrayAscending(trainers);
15
16 let matches: number = 0; // Initialize the number of matches to zero
17 let trainersIndex: number = 0; // Initialize the trainers index to the start of the array
18
19 // Iterate through each player and match with trainers based on strength
20 for (const playerStrength of sortedPlayers) {
21 // Find a trainer that can match the current player's strength
22 while (trainersIndex < sortedTrainers.length && sortedTrainers[trainersIndex] < playerStrength) {
23 trainersIndex++; // Increment trainers index if the current trainer is weaker than the player
24 }
25
26 // If a suitable trainer is found, make the match
27 if (trainersIndex < sortedTrainers.length) {
28 matches++; // Increment match count
29 trainersIndex++; // Move to the next trainer for the following players
30 }
31 }
32
33 return matches; // Return the total number of matches made
34}
35
36// Export the function if this is part of a module
37export { matchPlayersAndTrainers };
38
Time and Space Complexity
Time Complexity
The time complexity of the code is determined by the sorting operations and the subsequent for-loop with the inner while loop.
-
Sorting both the
players
andtrainers
list takesO(nlogn)
andO(mlogm)
, respectively, wheren
is the number of players andm
is the number of trainers. -
The for-loop iterates over each player, which is
O(n)
. Within this loop, the while loop progresses without resetting, which makes it linear overm
elements of trainers in total. In the worst case, all players are checked against all trainers, hence it contributes a maximum ofO(m)
time complexity.
The combined time complexity of these operations would be O(nlogn) + O(mlogm) + O(n + m)
. However, since O(nlogn)
and O(mlogm)
are the dominant terms, the overall time complexity simplifies to O(nlogn + mlogm)
.
Space Complexity
The space complexity of the code is O(1)
, which is the additional space required. The sorting happens in place, and no additional data structures are used aside from a few variables for keeping track of indexes and the answer.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced