Divide Players Into Teams of Equal Skill — LeetCode 2491 Python Solution

The problem

You are given a positive integer array skill of even length n where skill[i] denotes the skill of the ith player. Divide the players into n / 2 teams of size 2 such that the total skill of each team is equal.

Example

Input

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

Output

22

Explanation

Divide the players into the following teams: (1, 5), (2, 4), (3, 3), where each team has a total skill of 6.

Python solution

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        skill.sort()
        t = skill[0] + skill[-1]
        i, j = 0, len(skill) - 1
        ans = 0
        while i < j:
            if skill[i] + skill[j] != t:
                return -1
            ans += skill[i] * skill[j]
            i, j = i + 1, j - 1
        return ans

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 2491. Divide Players Into Teams of Equal Skill is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems