Divide Players Into Teams of Equal Skill — Solution
Divide Players Into Teams of Equal Skill solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Divide Players Into Teams of Equal Skill is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, 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
skill has an even length n; skill[i] is the skill of player i. Split the players into n / 2 teams of two so that every team has the same total skill.
The chemistry of a team is the product of its two players' skills. Return the sum of the chemistry of all teams, or -1 if no such split exists.
Note: the original problem allows 10^5 players and returns a 64-bit sum; here skill.length <= 2000, so the answer always fits in a 32-bit integer.
Example 1
Input: skill = [4,2,5,1,3,3]
Output: 22
Explanation: Teams `(1,5)`, `(2,4)` and `(3,3)` each total 6; chemistry 5 + 8 + 9 = 22.
Example 2
Input: skill = [2,7]
Output: 14
Example 3
Input: skill = [1,1,2,3]
Output: -1
Explanation: The total 7 cannot be split into two equal team totals.
Constraints
2 <= skill.length <= 2000skill.length is even1 <= skill[i] <= 1000
Hints for Divide Players Into Teams of Equal Skill
Hint 1
If a split exists, every team's total must be
2 * sum / n.Hint 2
The weakest player must be paired with the strongest one — otherwise the strongest one's team would be too strong.
Hint 3
Sort, pair
skill[i]withskill[n-1-i], and check every pair has the same total while summing the products.
How to solve Divide Players Into Teams of Equal Skill
Sorted, the only possible pairing is outermost-with-outermost: the smallest player must team up with the largest. So pairing the sorted ends inwards either works or proves no split exists.
Approach
- Sort
skillascending. - Let
target = skill[0] + skill[n-1]. - For
i = 0 .. n/2 - 1, pairskill[i]withskill[n-1-i]; if their sum differs fromtarget, return-1. - Otherwise add
skill[i] * skill[n-1-i]to the answer and return it.
Why it works
Suppose a valid split with common total T exists. The largest player M is paired with someone of skill T - M, which is the smallest possible partner value; if a smaller player m < T - M existed, its partner would need skill T - m > M, impossible. So the smallest and largest are paired, and removing them leaves the same situation on the rest — by induction, the end-to-end pairing is the only one, and the check is exact.
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- Checking only that the total is divisible by
n / 2is not enough —[1,1,2,4]has total 8 but no valid split. - Chemistry is a product per team, summed — not the product of team totals.
- With the original limits the sum needs 64 bits.
Reference solution
Python
from typing import List
def dividePlayers(skill: List[int]) -> int:
s = sorted(skill)
n = len(s)
target = s[0] + s[n - 1]
chem = 0
for i in range(n // 2):
a, b = s[i], s[n - 1 - i]
if a + b != target:
return -1
chem += a * b
return chemJava
public static int dividePlayers(int[] skill) {
int[] s = skill.clone();
Arrays.sort(s);
int n = s.length, target = s[0] + s[n - 1];
long chem = 0;
for (int i = 0; i < n / 2; i++) {
int a = s[i], b = s[n - 1 - i];
if (a + b != target) return -1;
chem += (long) a * b;
}
return (int) chem;
}C++
int dividePlayers(vector<int>& skill) {
vector<int> s(skill.begin(), skill.end());
sort(s.begin(), s.end());
int n = s.size(), target = s[0] + s[n - 1];
long long chem = 0;
for (int i = 0; i < n / 2; i++) {
int a = s[i], b = s[n - 1 - i];
if (a + b != target) return -1;
chem += (long long)a * b;
}
return (int)chem;
}JavaScript
var dividePlayers = function(skill) {
var s = skill.slice().sort(function(a, b) { return a - b; });
var n = s.length, target = s[0] + s[n - 1], chem = 0;
for (var i = 0; i < n / 2; i++) {
var a = s[i], b = s[n - 1 - i];
if (a + b !== target) return -1;
chem += a * b;
}
return chem;
};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 · Hashing: Hash Maps and Hash Sets