Divide Players Into Teams of Equal Skill

Medium Arrays & Hashing Two Pointer Original on LeetCode

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^5
  • skill.length is 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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (search a partner for each player)O(n²)O(n)
Sort and pair the endsO(n log n)O(1)
Optimal (counting array)O(n + K)O(K)

1Brute force (search a partner for each player)

TimeO(n²)Each player may scan all others for a partner.
SpaceO(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.

  1. If total % (n / 2) != 0 return -1; T = total / (n / 2).
  2. For each unpaired i, scan j > i for an unpaired player with skill[j] == T - skill[i].
  3. 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;
    }
}

2Sort and pair the ends

TimeO(n log n)Sorting dominates; the pairing pass is linear.
SpaceO(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.

  1. Sort the skills.
  2. T = skill[0] + skill[n - 1].
  3. 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;
    }
}

3Optimal (counting array)

TimeO(n + K)One counting pass plus one pass over the K = 1000 possible values.
SpaceO(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.

  1. If total % teams != 0 return -1; T = total / teams.
  2. Count each skill in cnt[0..1000].
  3. 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.
  4. 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;
    }
}

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).