Divide Players Into Teams of Equal Skill
MedPrompt
You are given a positive integer array skill of even length n where skill[i] denotes the skill of the ith player. Divide the players into n / 2 teams of size 2 such that the total skill of each team is equal.
The chemistry of a team is equal to the product of the skills of the players on that team.
Return the sum of the chemistry of all the teams, or return -1 if there is no way to divide the players into teams such that the total skill of each team is equal.
Example 1:
Input: skill = [3,2,5,1,3,4]
Output: 22
Explanation:
Divide the players into the following teams: (1, 5), (2, 4), (3, 3), where each team has a total skill of 6.
The sum of the chemistry of all the teams is: 1 * 5 + 2 * 4 + 3 * 3 = 5 + 8 + 9 = 22.Example 2:
Input: skill = [3,4]
Output: 12
Explanation:
The two players form a team with a total skill of 7.
The chemistry of the team is 3 * 4 = 12.Example 3:
Input: skill = [1,1,2,3]
Output: -1
Explanation:
There is no way to divide the players into teams such that the total skill of each team is equal.
Constraints:
2 <= skill.length <= 105skill.lengthis even.1 <= skill[i] <= 1000
Approaches
3 approaches with complexity analysis and trade-offs.
The core idea of this brute-force approach is to systematically try every possible valid target sum for the teams. A potential target sum can be determined by picking a fixed player, say skill[0], and pairing them with every other player, skill[i]. This generates n-1 candidate target sums.
For each candidate target_sum, we then verify if it's possible to partition all n players into n/2 teams, where each team's skill sum equals this target_sum. To do this check efficiently, we use a frequency map (e.g., a HashMap) to count the occurrences of each skill. We then iterate through our map, and for each skill k, we check if its required partner (target_sum - k) exists in the map with the necessary frequency. If we can successfully pair up all players for a given target_sum, we calculate the total chemistry and return it. If we exhaust all n-1 possibilities without success, no solution exists.
Algorithm
- Iterate through each player
skill[i](wherei > 0) to be a potential partner for the first player,skill[0]. - For each
i, define a potential target sum for all teams:target_sum = skill[0] + skill[i]. - Create a frequency map of all skills in the input array to count occurrences of each skill value.
- For the current
target_sum, attempt to partition all players inton/2teams. This can be done by iterating through the skills and their counts in the frequency map. - For each skill
kin the map, its required partner isp = target_sum - k. Check ifpexists in the map with a sufficient count. - If
k == p, the count ofkmust be even. Ifk != p, the count ofkmust equal the count ofp. - If a valid partner cannot be found for any skill, this
target_sumis invalid. Break and try the nexttarget_sum. - If all players can be paired up successfully, calculate the total chemistry and return it.
- If the main loop finishes without finding any valid
target_sum, it's impossible to partition the players as required. Return -1.
Walkthrough
import java.util.Map;import java.util.HashMap; class Solution { public long dividePlayers(int[] skill) { int n = skill.length; if (n % 2 != 0) { return -1; } // Try every other player as a partner for skill[0] for (int i = 1; i < n; i++) { long targetSum = skill[0] + skill[i]; Map<Integer, Integer> freq = new HashMap<>(); for (int s : skill) { freq.put(s, freq.getOrDefault(s, 0) + 1); } long currentChemistry = 0; boolean possible = true; for (int s : skill) { // If skill s has already been paired, its count will be 0 if (freq.getOrDefault(s, 0) > 0) { int partnerSkill = (int) (targetSum - s); // Decrement current skill's count freq.put(s, freq.get(s) - 1); // Check for partner if (freq.getOrDefault(partnerSkill, 0) > 0) { freq.put(partnerSkill, freq.get(partnerSkill) - 1); currentChemistry += (long) s * partnerSkill; } else { // No partner found, this targetSum is not possible possible = false; break; } } } if (possible) { // Each pair's chemistry was added twice (once for s, once for partner) return currentChemistry / 2; } } return -1; }}Complexity
Time
O(n^2). The outer loop runs `n-1` times to select a partner for `skill[0]`. Inside this loop, we build a frequency map (`O(n)`) and then iterate through the skills again to check for pairs (`O(n)`), resulting in a quadratic time complexity.
Space
O(K) or O(n), where K is the number of unique skills. A frequency map is used to store skill counts. In the worst case, all `n` skills are unique, leading to `O(n)` space.
Trade-offs
Pros
It's a straightforward brute-force method that explores all possibilities stemming from the first player's pairing.
It does not require modifying the original input array (no sorting).
Cons
The time complexity of
O(n^2)is too slow for the given constraints (nup to 10^5), leading to a 'Time Limit Exceeded' error on larger test cases.The implementation is more complex than the optimal solution, involving nested loops and careful management of the frequency map.
A much more efficient approach relies on a key insight: if a valid set of teams can be formed, the player with the lowest skill must be paired with the player with the highest skill. Why? If the lowest-skill player were paired with anyone else, the highest-skill player would need a partner with a skill lower than the minimum possible skill to match the team sum, which is a contradiction.
This logic extends inwards. After pairing the lowest and highest, the second-lowest must be paired with the second-highest, and so on. This leads to a simple and elegant algorithm. First, we sort the skill array. Then, we use a two-pointer technique. One pointer starts at the beginning (left), and the other at the end (right). We check if skill[left] + skill[right] is constant for all pairs as we move the pointers towards the center. If it is, we sum up the chemistries; otherwise, no solution exists.
Algorithm
- Sort the
skillarray in non-decreasing order. - The player with the minimum skill is now at
skill[0]and the maximum is atskill[n-1]. If a solution exists, they must be paired together. Their sum defines the single possible target sum for all teams:target_sum = skill[0] + skill[n-1]. - Initialize two pointers:
leftat the start of the array (index 0) andrightat the end (indexn-1). - Initialize a variable
total_chemistryto 0. - Loop while
left < right: a. Check if the sum of the skills at the pointers,skill[left] + skill[right], equalstarget_sum. b. If the sum is not equal totarget_sum, a valid division is impossible. Return -1. c. If the sum is equal, this is a valid team. Add their chemistry,(long)skill[left] * skill[right], tototal_chemistry. d. Move the pointers inwards to consider the next pair:left++andright--. - If the loop completes, all players have been successfully paired. Return
total_chemistry.
Walkthrough
import java.util.Arrays; class Solution { public long dividePlayers(int[] skill) { int n = skill.length; // Sort the array to easily pair lowest with highest skill players Arrays.sort(skill); // The target sum for each team is determined by the first and last elements long targetSum = skill[0] + skill[n - 1]; long totalChemistry = 0; // Use two pointers to form teams from the ends of the sorted array int left = 0; int right = n - 1; while (left < right) { // Check if the current pair has the required sum if (skill[left] + skill[right] != targetSum) { return -1; // If not, a valid division is impossible } // Add the chemistry of the current team to the total totalChemistry += (long) skill[left] * skill[right]; // Move to the next pair left++; right--; } return totalChemistry; }}Complexity
Time
O(n log n). The time complexity is dominated by the initial sorting of the `skill` array. The subsequent two-pointer scan runs in `O(n)` time.
Space
O(log n) to O(n). The space complexity depends on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitives uses a variant of Quicksort, which requires `O(log n)` space on average for the recursion stack, and `O(n)` in the worst case.
Trade-offs
Pros
Highly efficient with
O(n log n)time complexity, which passes all constraints.The logic is simple to understand and implement.
It is guaranteed to find the unique valid pairing if one exists.
Cons
The
O(n log n)time complexity is determined by the sorting step. While very good, it's technically not linear time.The approach requires modifying the input array by sorting it. If the original order must be preserved, a copy of the array should be made first, which would use
O(n)extra space.
This approach is a further optimization of the sorting-based method. Given the constraint that skill values are in a limited range (1 to 1000), we can replace the O(n log n) comparison-based sort with a linear time sorting algorithm like Counting Sort. This improves the overall time complexity to be linear.
First, we create a frequency array to count the occurrences of each skill value. This takes O(n + K) time, where K is the range of skills. Then, instead of using pointers on a sorted array, we use pointers on the frequency array itself to find the current minimum and maximum available skills to pair. We repeatedly pair the smallest available skill with the largest available skill, check if their sum matches the target, and accumulate the chemistry. This avoids the log n factor from sorting, making it the most efficient solution.
Algorithm
- Since skill values are bounded (
1 <= skill[i] <= 1000), we can use a non-comparison sort. Create a frequency array,counts, of size 1001. - Iterate through the input
skillarray once to populate thecountsarray and simultaneously find the minimum (minSkill) and maximum (maxSkill) skill values present. - The target sum for all teams is fixed:
target_sum = minSkill + maxSkill. - Initialize
total_chemistryto 0. - Loop
n/2times to form then/2teams. a. In each iteration, we need to find the current smallest available skill and the current largest available skill. We can use two pointers,leftandright, starting atminSkillandmaxSkillrespectively. b. Advance theleftpointer until it finds a skilllwherecounts[l] > 0. c. Advance therightpointer until it finds a skillrwherecounts[r] > 0. d. Check ifl + requalstarget_sum. If not, return -1. e. If they match, form a team. Add their chemistry(long)l * rtototal_chemistry. f. Decrement the counts for these two skills:counts[l]--andcounts[r]--. - After the loop finishes, return
total_chemistry.
Walkthrough
class Solution { public long dividePlayers(int[] skill) { int n = skill.length; int MAX_SKILL = 1000; int[] counts = new int[MAX_SKILL + 1]; int minSkill = Integer.MAX_VALUE; int maxSkill = Integer.MIN_VALUE; for (int s : skill) { counts[s]++; minSkill = Math.min(minSkill, s); maxSkill = Math.max(maxSkill, s); } long targetSum = minSkill + maxSkill; long totalChemistry = 0; int left = minSkill; int right = maxSkill; // We need to form n/2 teams for (int i = 0; i < n / 2; i++) { // Find the next available smallest skill while (counts[left] == 0) { left++; } // Find the next available largest skill while (counts[right] == 0) { right--; } // Check if this pair matches the target sum if (left + right != targetSum) { return -1; } // Add chemistry and "use up" the players for this team totalChemistry += (long) left * right; counts[left]--; counts[right]--; } return totalChemistry; }}Complexity
Time
O(n + K). Populating the frequency array takes `O(n)`. The main loop runs `n/2` times, and the two pointers (`left` and `right`) together traverse the range of skills `K` at most once. Thus, the total time is linear.
Space
O(K), where `K` is the range of skill values (1000). We use an auxiliary `counts` array of size `K+1`. Since `K` is a constant, this is considered `O(1)` space.
Trade-offs
Pros
Achieves the best possible time complexity of
O(n + K), which is linear.Space complexity is constant with respect to
n, as it only depends on the fixed range of skill values (K).
Cons
This approach is specialized. Its efficiency relies on the constraint that skill values fall within a small, fixed range. It would not be efficient if the skill values could be arbitrarily large.
Solutions
Solution
class Solution {public long dividePlayers(int[] skill) { Arrays.sort(skill); int n = skill.length; int t = skill[0] + skill[n - 1]; long ans = 0; for (int i = 0, j = n - 1; i < j; ++i, --j) { if (skill[i] + skill[j] != t) { return -1; } ans += (long)skill[i] * skill[j]; } return ans; }}var dividePlayers = function ( skill ) { const n = skill . length , m = n / 2 ; skill . sort (( a , b ) => a - b ); const sum = skill [ 0 ] + skill [ n - 1 ]; let ans = 0 ; for ( let i = 0 ; i < m ; i ++ ) { const x = skill [ i ], y = skill [ n - 1 - i ]; if ( x + y != sum ) return - 1 ; ans += x * y ; } return ans ; };class Solution { public: long long dividePlayers ( vector < int >& skill ) { sort ( skill . begin (), skill . end ()); int n = skill . size (); int t = skill [ 0 ] + skill [ n - 1 ]; long long ans = 0 ; for ( int i = 0 , j = n - 1 ; i < j ; ++ i , -- j ) { if ( skill [ i ] + skill [ j ] != t ) return - 1 ; ans += 1ll * skill [ i ] * skill [ j ]; } return ans ; } };class Solution: def dividePlayers(self, skill: List[int]) -> int: skill . sort() t = skill[0] + skill[- 1] i, j = 0, len(skill) - 1 ans = 0 while i < j: if skill[i] + skill[j] != t: return - 1 ans += skill[i] * skill[j] i, j = i + 1, j - 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.