Divide Players Into Teams of Equal Skill

Medium
1166.

Divide Players Into Teams of Equal Skill

Divide Players Into Teams of Equal Skill is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.

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 <= 2000
  • skill.length is even
  • 1 <= skill[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} skill
 * @return {number}
 */
var dividePlayers = function(skill) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 2000
  • skill.length is even
  • 1 <= skill[i] <= 1000

Hints for Divide Players Into Teams of Equal Skill

  1. Hint 1

    If a split exists, every team's total must be 2 * sum / n.

  2. Hint 2

    The weakest player must be paired with the strongest one — otherwise the strongest one's team would be too strong.

  3. Hint 3

    Sort, pair skill[i] with skill[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

  1. Sort skill ascending.
  2. Let target = skill[0] + skill[n-1].
  3. For i = 0 .. n/2 - 1, pair skill[i] with skill[n-1-i]; if their sum differs from target, return -1.
  4. 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 / 2 is 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 chem

Java

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