Divide Players Into Teams of Equal Skill
Divide Players Into Teams of Equal Skill is a medium arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (counting array), runs in O(n + K) time and O(K) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (search a partner for each player) up.
Problem
There are an even number of players, and skill[i] is the skill of player i. Split them into teams of exactly two, so that every team has the same total skill.
The chemistry of a team is the product of its two skills. Return the sum of the chemistry of all teams, or -1 if no such division is possible.
Examples
Example 1
- Input
skill = [4, 1, 3, 2, 3, 2]- Output
16- Why
- Teams (4, 1), (3, 2), (3, 2) each total 5. The chemistry sum is 4 + 6 + 6 = 16.
Example 2
- Input
skill = [6, 6]- Output
36- Why
- One team of two players; its chemistry is 6 · 6.
Example 3
- Input
skill = [1, 2, 3, 5]- Output
-1- Why
- The total 11 cannot be split evenly between 2 teams, so no valid division exists.
Constraints
2 <= skill.length <= 10^5skill.lengthis even.1 <= skill[i] <= 1000
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (search a partner for each player) | O(n²) | O(n) |
| Sort and pair the ends | O(n log n) | O(1) |
| Optimal (counting array) | O(n + K) | O(K) |
1Brute force (search a partner for each player)
O(n²)Each player may scan all others for a partner.O(n)The used flags.Compute the required team total T. Go through the players; for each one still unpaired, scan the rest for an unpaired player with skill T - x. If none exists, the division is impossible.
- If total % (n / 2) != 0 return -1; T = total / (n / 2).
- For each unpaired i, scan j > i for an unpaired player with skill[j] == T - skill[i].
- If found, mark both and add skill[i] · skill[j]; otherwise return -1.
class Solution {
public long dividePlayers(int[] skill) {
int n = skill.length, teams = n / 2;
long total = 0;
for (int s : skill) total += s;
if (total % teams != 0) return -1;
long target = total / teams;
boolean[] used = new boolean[n];
long chemistry = 0;
for (int i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = true;
int partner = -1;
for (int j = i + 1; j < n; j++) {
if (!used[j] && skill[i] + skill[j] == target) { partner = j; break; }
}
if (partner == -1) return -1;
used[partner] = true;
chemistry += (long) skill[i] * skill[partner];
}
return chemistry;
}
}class Solution:
def dividePlayers(self, skill: List[int]) -> int:
n = len(skill)
teams = n // 2
total = sum(skill)
if total % teams != 0:
return -1
target = total // teams
used = [False] * n
chemistry = 0
for i in range(n):
if used[i]:
continue
used[i] = True
partner = -1
for j in range(i + 1, n):
if not used[j] and skill[i] + skill[j] == target:
partner = j
break
if partner == -1:
return -1
used[partner] = True
chemistry += skill[i] * skill[partner]
return chemistryclass Solution {
public:
long long dividePlayers(vector<int>& skill) {
int n = skill.size(), teams = n / 2;
long long total = 0;
for (int s : skill) total += s;
if (total % teams != 0) return -1;
long long target = total / teams;
vector<bool> used(n, false);
long long chemistry = 0;
for (int i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = true;
int partner = -1;
for (int j = i + 1; j < n; j++) {
if (!used[j] && skill[i] + skill[j] == target) { partner = j; break; }
}
if (partner == -1) return -1;
used[partner] = true;
chemistry += (long long)skill[i] * skill[partner];
}
return chemistry;
}
};function dividePlayers(skill) {
const n = skill.length, teams = n / 2;
let total = 0;
for (const s of skill) total += s;
if (total % teams !== 0) return -1;
const target = total / teams;
const used = new Array(n).fill(false);
let chemistry = 0;
for (let i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = true;
let partner = -1;
for (let j = i + 1; j < n; j++) {
if (!used[j] && skill[i] + skill[j] === target) { partner = j; break; }
}
if (partner === -1) return -1;
used[partner] = true;
chemistry += skill[i] * skill[partner];
}
return chemistry;
}2Sort and pair the ends
O(n log n)Sorting dominates; the pairing pass is linear.O(1)Sorting in place (ignoring the sort's own stack).If a valid division exists, the weakest player must be paired with the strongest (anyone else would leave the strongest player needing an even weaker partner). Sort, then pair index i with n - 1 - i and check every pair has the same total.
- Sort the skills.
- T = skill[0] + skill[n - 1].
- For i < n / 2: if skill[i] + skill[n - 1 - i] != T return -1; else add their product.
class Solution {
public long dividePlayers(int[] skill) {
Arrays.sort(skill);
int n = skill.length;
int target = skill[0] + skill[n - 1];
long chemistry = 0;
for (int i = 0, j = n - 1; i < j; i++, j--) {
if (skill[i] + skill[j] != target) return -1;
chemistry += (long) skill[i] * skill[j];
}
return chemistry;
}
}class Solution:
def dividePlayers(self, skill: List[int]) -> int:
skill.sort()
n = len(skill)
target = skill[0] + skill[n - 1]
chemistry = 0
i, j = 0, n - 1
while i < j:
if skill[i] + skill[j] != target:
return -1
chemistry += skill[i] * skill[j]
i += 1
j -= 1
return chemistryclass Solution {
public:
long long dividePlayers(vector<int>& skill) {
sort(skill.begin(), skill.end());
int n = skill.size();
int target = skill[0] + skill[n - 1];
long long chemistry = 0;
for (int i = 0, j = n - 1; i < j; i++, j--) {
if (skill[i] + skill[j] != target) return -1;
chemistry += (long long)skill[i] * skill[j];
}
return chemistry;
}
};function dividePlayers(skill) {
skill.sort((a, b) => a - b);
const n = skill.length;
const target = skill[0] + skill[n - 1];
let chemistry = 0;
for (let i = 0, j = n - 1; i < j; i++, j--) {
if (skill[i] + skill[j] !== target) return -1;
chemistry += skill[i] * skill[j];
}
return chemistry;
}3Optimal (counting array)
O(n + K)One counting pass plus one pass over the K = 1000 possible values.O(K)The count array of size K + 1.Skills are at most 1000, so count them. With T = total / teams, every value v needs exactly as many partners of value T - v as there are players with value v. Summing cnt[v] · v · (T - v) over all values counts each team twice, so halve it at the end.
- If total % teams != 0 return -1; T = total / teams.
- Count each skill in cnt[0..1000].
- For each v with cnt[v] > 0: w = T - v must be in 1..1000 with cnt[w] == cnt[v] (and cnt[v] even when w == v), else return -1.
- Add cnt[v] · v · w; return the sum / 2.
class Solution {
public long dividePlayers(int[] skill) {
int teams = skill.length / 2;
long total = 0;
int[] cnt = new int[1001];
for (int s : skill) {
total += s;
cnt[s]++;
}
if (total % teams != 0) return -1;
int target = (int) (total / teams);
long sum = 0;
for (int v = 1; v <= 1000; v++) {
if (cnt[v] == 0) continue;
int w = target - v;
if (w < 1 || w > 1000 || cnt[w] != cnt[v]) return -1;
if (w == v && cnt[v] % 2 != 0) return -1;
sum += (long) cnt[v] * v * w;
}
return sum / 2;
}
}class Solution:
def dividePlayers(self, skill: List[int]) -> int:
teams = len(skill) // 2
total = sum(skill)
if total % teams != 0:
return -1
target = total // teams
cnt = [0] * 1001
for s in skill:
cnt[s] += 1
result = 0
for v in range(1, 1001):
if cnt[v] == 0:
continue
w = target - v
if w < 1 or w > 1000 or cnt[w] != cnt[v]:
return -1
if w == v and cnt[v] % 2 != 0:
return -1
result += cnt[v] * v * w
return result // 2class Solution {
public:
long long dividePlayers(vector<int>& skill) {
int teams = skill.size() / 2;
long long total = 0;
vector<int> cnt(1001, 0);
for (int s : skill) {
total += s;
cnt[s]++;
}
if (total % teams != 0) return -1;
int target = (int)(total / teams);
long long sum = 0;
for (int v = 1; v <= 1000; v++) {
if (cnt[v] == 0) continue;
int w = target - v;
if (w < 1 || w > 1000 || cnt[w] != cnt[v]) return -1;
if (w == v && cnt[v] % 2 != 0) return -1;
sum += (long long)cnt[v] * v * w;
}
return sum / 2;
}
};function dividePlayers(skill) {
const teams = skill.length / 2;
let total = 0;
const cnt = new Array(1001).fill(0);
for (const s of skill) {
total += s;
cnt[s]++;
}
if (total % teams !== 0) return -1;
const target = total / teams;
let sum = 0;
for (let v = 1; v <= 1000; v++) {
if (cnt[v] === 0) continue;
const w = target - v;
if (w < 1 || w > 1000 || cnt[w] !== cnt[v]) return -1;
if (w === v && cnt[v] % 2 !== 0) return -1;
sum += cnt[v] * v * w;
}
return sum / 2;
}Edge cases to test
- Exactly two players (always valid)
- Total skill not divisible by the number of teams
- A divisible total whose values still cannot be paired, like [1, 1, 2, 4] (team total 4, but no 3 exists for the 1s)
- All players with the same skill
- The answer can exceed the 32-bit range (use a 64-bit sum)
Hints
Hint 1
Every team must have the same total, so that total is fixed: sum of all skills divided by the number of teams.
Hint 2
Once the team total T is known, a player with skill x must be paired with a player of skill T - x.
Hint 3
After sorting, the smallest must pair with the largest. With skills at most 1000, counting replaces sorting.
FAQ
What is the best time complexity for Divide Players Into Teams of Equal Skill?
Optimal (counting array) runs in O(n + K) time and O(K) extra space. One counting pass plus one pass over the K = 1000 possible values.
Which pattern does Divide Players Into Teams of Equal Skill use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for Divide Players Into Teams of Equal Skill?
Yes. Brute force (search a partner for each player) takes O(n²) time and O(n) space. Compute the required team total T.
Which edge cases should I test for Divide Players Into Teams of Equal Skill?
Exactly two players (always valid); Total skill not divisible by the number of teams; A divisible total whose values still cannot be paired, like [1, 1, 2, 4] (team total 4, but no 3 exists for the 1s); All players with the same skill; The answer can exceed the 32-bit range (use a 64-bit sum).