Medium

Divide Players Into Teams of Equal Skill

LAB

Pair players so every pair has the same total skill. Return the sum of pair chemistry products, or -1 if impossible.

EXAMPLES

Example 1

Input
{
  "skill": [
    3,
    2,
    5,
    1,
    3,
    4
  ]
}

Output
22

FUNCTION SHAPE

skill: intArray→int

SOLUTION NOTE

Classic two pointers from opposite ends. After sorting, pair the smallest with the largest. All pairs must have the same sum (target = skill[0] + skill[-1]). If any pair doesn't match the target, return -1.

Reveal reference solution +

pythonREFERENCE

def dividePlayers(self, skill: List[int]) -> int:
    skill.sort()
    n = len(skill)
    target = skill[0] + skill[-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 chemistry

TimeO(n log n)

SpaceO(1)

Open on LeetCode ↗