Divide Players Into Teams of Equal Skill

medium two pointers sorting greedy

Problem

You are given an even-length array skill of positive integers. Divide the players into n / 2 teams of two so that every team has the same total skill. A team's chemistry is the product of its two skills. Return the sum of all teams' chemistry, or -1 if no equal-total division exists.

Inputskill = [3,2,5,1,3,4]

Output22

Teams (1,5), (2,4), (3,3) each total 6. Chemistry = 1·5 + 2·4 + 3·3 = 22.

Inputskill = [1,1,2,3]

Output-1

No pairing gives every team the same total skill.

skill (comma-separated, even count)

def divide_players(skill):
    skill.sort()
    n = len(skill)
    i, j = 0, n - 1
    target = skill[0] + skill[n - 1]
    total = 0
    while i < j:
        if skill[i] + skill[j] != target:
            return -1
        total += skill[i] * skill[j]
        i += 1
        j -= 1
    return total

function dividePlayers(skill) {
  skill.sort((a, b) => a - b);
  const n = skill.length;
  let i = 0, j = n - 1;
  const target = skill[0] + skill[n - 1];
  let total = 0;
  while (i < j) {
    if (skill[i] + skill[j] !== target) return -1;
    total += skill[i] * skill[j];
    i++;
    j--;
  }
  return total;
}

long dividePlayers(int[] skill) {
    Arrays.sort(skill);
    int n = skill.length;
    int i = 0, j = n - 1;
    int target = skill[0] + skill[n - 1];
    long total = 0;
    while (i < j) {
        if (skill[i] + skill[j] != target) return -1;
        total += (long) skill[i] * skill[j];
        i++;
        j--;
    }
    return total;
}

long long dividePlayers(vector<int>& skill) {
    sort(skill.begin(), skill.end());
    int n = skill.size();
    int i = 0, j = n - 1;
    int target = skill[0] + skill[n - 1];
    long long total = 0;
    while (i < j) {
        if (skill[i] + skill[j] != target) return -1;
        total += (long long) skill[i] * skill[j];
        i++;
        j--;
    }
    return total;
}

Explanation

If every team must have the same total skill, then the strongest player can only be paired with the weakest, the second strongest with the second weakest, and so on. Any other pairing would let one team exceed the smallest possible team total.

So we sort the array and apply the classic two-pointer sweep: pointer i starts at the smallest value, pointer j at the largest. After sorting, the required team total is fixed: target = skill[0] + skill[n - 1].

At each step we form the team (skill[i], skill[j]). If its sum does not equal target, an equal division is impossible and we immediately return -1. Otherwise we add this team's chemistry skill[i] * skill[j] to the running total and move both pointers inward.

The loop runs until the pointers meet, having considered all n / 2 teams. Because the array is sorted, checking against a single fixed target is enough — there is no need to search for partners.

Sorting dominates the cost at O(n log n); the pointer sweep is linear. Use a 64-bit accumulator for total since the sum of products can exceed 32-bit range on large inputs.

Time: O(n log n) Space: O(1)