Leetcode 2491: Divide Players Into Teams of Equal Skill
You are given an array of integers representing the skill levels of players. You need to divide the players into pairs such that the sum of the skill levels of each pair is the same across all pairs. If it’s possible to form such pairs, return the sum of their chemistry, which is the product of the skill levels in each pair. If no such division is possible, return -1.
Problem
Approach
Steps
Complexity
Input: The input is a list of integers where each integer represents the skill level of a player.
Example: skill = [1, 5, 2, 4, 3, 3]
Constraints:
• 2 <= skill.length <= 100000
• skill.length is always even.
• 1 <= skill[i] <= 1000
Output: Return the sum of the chemistry for all valid pairs, or -1 if it's impossible to form the pairs.
Example: Output: 22
Constraints:
• The sum of chemistry values will be computed only for valid teams.
Goal: The goal is to check if the players can be divided into pairs with equal total skill level, and calculate the sum of their chemistry.
Steps:
• 1. Sort the skill levels of players.
• 2. Check if the sum of the first and last skill levels in the sorted array is the same for all adjacent pairs.
• 3. If the total skill sum is the same for all pairs, calculate the chemistry for each pair and return the sum. Otherwise, return -1.
Goal: The input contains an even number of players and their skill levels are positive integers between 1 and 1000.
Steps:
• skill.length is always even.
• Players' skill levels are positive integers between 1 and 1000.
Assumptions:
• Players' skill levels are always valid positive integers.
• There will always be an even number of players in the input.
• Input: skill = [1, 5, 2, 4, 3, 3]
• Explanation: Here, after sorting the array, the players form pairs (1, 5), (2, 4), and (3, 3) which have equal total skill (6). The chemistry is calculated as 1*5 + 2*4 + 3*3 = 5 + 8 + 9 = 22.
• Input: skill = [1, 2, 3, 4]
• Explanation: This input cannot form valid pairs because the total skill sum of any pair does not match, so the output is -1.
• Input: skill = [3, 4]
• Explanation: With only two players, they form a valid pair with a sum of 7, and the chemistry is 3*4 = 12.
Approach: To solve this problem, we first sort the array to make pairing easier and check if all pairs have the same total skill level.
Observations:
• The problem requires ensuring the total skill for each pair is consistent.
• Sorting the array allows easier pairing of players with compatible skill levels.
• Sorting the array helps in pairing the smallest and largest available players to achieve a balanced sum.
Steps:
• 1. Sort the skill array.
• 2. Set the first pair sum by adding the first and last elements of the sorted array.
• 3. Iterate through the array, forming pairs and checking if their sum matches the first pair sum.
• 4. Calculate the product for each valid pair and sum them up.
Empty Inputs:
• The input will always contain an even number of players and won't be empty.
Large Inputs:
• For large inputs, ensure the sorting operation and pair checking runs efficiently.
Special Values:
• The skill levels are between 1 and 1000, so there will be no zero or negative skill levels.
Constraints:
• Ensure efficient handling of the upper limit of skill array length (up to 100,000 players).
long long dividePlayers(vector<int>& skill) {
sort(skill.begin(), skill.end());
int n = skill.size();
int l = 0, r = n - 1;
int sum = skill[l] + skill[r];
long long prod = skill[l] * skill[r];
l++, r--;
while(l < r) {
if(sum != (skill[l] + skill[r])) return -1;
prod += skill[l] * skill[r];
l++;
r--;
}
return prod;
}
1 : Function Declaration
long long dividePlayers(vector<int>& skill) {
This line declares the function `dividePlayers`, which takes a vector `skill` representing the skill levels of players and returns a `long long` value representing the total product of paired skills.
2 : Sorting
sort(skill.begin(), skill.end());
This line sorts the `skill` vector in ascending order to facilitate pairing the weakest and strongest players.
3 : Variable Initialization
int n = skill.size();
This line initializes the variable `n` to the size of the `skill` vector, representing the total number of players.
4 : Pointers Initialization
int l = 0, r = n - 1;
Here, two pointers, `l` (left) and `r` (right), are initialized to point to the first and last elements of the sorted `skill` vector, respectively.
5 : Sum Calculation
int sum = skill[l] + skill[r];
This line calculates the sum of the skills of the leftmost (`l`) and rightmost (`r`) players.
6 : Product Calculation
long long prod = skill[l] * skill[r];
Here, the product of the skills of the leftmost and rightmost players is calculated and stored in `prod`.
7 : Pointer Adjustment
l++, r--;
The pointers `l` and `r` are moved inward, `l` is incremented, and `r` is decremented.
8 : Loop Start
while(l < r) {
This while loop runs as long as the left pointer is less than the right pointer, processing each pair of players.
9 : Sum Validation
if(sum != (skill[l] + skill[r])) return -1;
Inside the loop, the sum of the current pair of players' skills is checked. If it does not match the sum of the first pair, `-1` is returned indicating an invalid division.
10 : Product Update
prod += skill[l] * skill[r];
If the sum is valid, the product of the current pair of skills is added to `prod`.
11 : Pointer Update
l++;
The left pointer `l` is incremented to move to the next player.
12 : Pointer Update
r--;
The right pointer `r` is decremented to move to the next player.
13 : Return Statement
return prod;
Once all pairs have been processed, the function returns the total product of the pairs' skills.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is dominated by the sorting operation, which is O(n log n), where n is the length of the skill array.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space required for the sorted array, but it could be reduced to O(1) if sorting is done in place.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus