LeetCode 2491 - Divide Players Into Teams of Equal Skill

This problem asks us to divide a given list of player skill levels into teams of exactly two players such that every team has the same total skill.

leetcodemediumarrayhash-tabletwo-pointerssorting

LeetCode Problem 2491

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Two Pointers, Sorting

Solution

Problem Understanding

This problem asks us to divide a given list of player skill levels into teams of exactly two players such that every team has the same total skill. The chemistry of a team is defined as the product of the skills of the two players, and we are asked to return the sum of the chemistry of all teams if such a division is possible. If it is not possible to divide players into teams with equal total skill, we must return -1.

The input is a list skill of even length n, where each element represents a player's skill level. Since the list length is even, it is guaranteed that we can pair up all players, but the challenge is to do so such that the sum of the skills in each pair is the same. The constraints, 2 <= skill.length <= 10^5 and 1 <= skill[i] <= 1000, indicate that we need an algorithm faster than O(n^2), as a naive brute-force approach will be too slow.

Important edge cases include: a minimal input of two players, inputs where all players have the same skill, and inputs where it is impossible to divide players into equal-skill teams.

Approaches

Brute Force

The brute-force approach would attempt all possible ways to pair up players and check if the sum of each pair is equal. This involves generating all permutations of pairings and verifying the sum constraint, then computing the chemistry. While this guarantees correctness, the number of pairings grows factorially with n, resulting in a time complexity of O(n!) which is infeasible for n up to 10^5.

Optimal Approach

The key insight for a faster solution is that if the total skill of each team is the same, then the sum of the minimum skill and maximum skill in a sorted array should equal this total. Sorting the array allows us to pair the smallest skill with the largest skill, the second smallest with the second largest, and so on. If at any point the sum of a pair does not equal the expected total, it is impossible to form equal-skill teams.

By using this approach, we only need to sort the array (O(n log n)) and then iterate over half the array to compute chemistry (O(n)). This yields an efficient and scalable solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Check all possible pairings of players. Impractical for large n.
Optimal O(n log n) O(1) Sort the array, pair smallest with largest, and check sums. Compute chemistry.

Algorithm Walkthrough

  1. Sort the array skill in ascending order. Sorting allows us to systematically pair the smallest and largest skill players to maximize the chances of equal-sum teams.

  2. Determine the expected team total skill by summing the first and last element in the sorted array. This is the total skill that all pairs must equal.

  3. Initialize a variable total_chemistry to 0, which will accumulate the product of each pair.

  4. Iterate with two pointers, one starting at the beginning of the array (left) and one at the end (right), and perform the following:

  5. Compute the sum of the pair: skill[left] + skill[right].

  6. If the sum does not equal the expected total, return -1 immediately.

  7. Otherwise, compute the product (chemistry) and add it to total_chemistry.

  8. Move the left pointer forward and right pointer backward.

  9. After completing the iteration, return total_chemistry.

Why it works: Sorting and pairing smallest with largest ensures that if a valid division exists, this strategy will find it. If any pair violates the expected total skill, it is impossible to create equal-skill teams. This approach uses the invariant that for any valid set of equal-skill pairs, the smallest and largest values must form a team.

Python Solution

from typing import List

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        skill.sort()
        n = len(skill)
        total_skill = skill[0] + skill[-1]
        total_chemistry = 0
        
        left, right = 0, n - 1
        while left < right:
            if skill[left] + skill[right] != total_skill:
                return -1
            total_chemistry += skill[left] * skill[right]
            left += 1
            right -= 1
            
        return total_chemistry

Implementation walkthrough: The code first sorts the skill array. total_skill is the target sum for all pairs. Two pointers iterate from the extremes of the array toward the center, verifying sums and accumulating chemistry. If any pair sum is incorrect, the function returns -1.

Go Solution

import "sort"

func dividePlayers(skill []int) int64 {
    sort.Ints(skill)
    n := len(skill)
    totalSkill := skill[0] + skill[n-1]
    var totalChemistry int64 = 0
    
    left, right := 0, n-1
    for left < right {
        if skill[left]+skill[right] != totalSkill {
            return -1
        }
        totalChemistry += int64(skill[left]) * int64(skill[right])
        left++
        right--
    }
    
    return totalChemistry
}

Go-specific notes: We use int64 for totalChemistry to handle large products that may exceed int. Sorting is done via the standard sort.Ints. Two-pointer iteration works similarly to Python, with explicit type conversion for multiplication.

Worked Examples

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

Step left right skill[left]+skill[right] product total_chemistry
Initial sorted: [1,2,3,3,4,5] 0 5 1+5=6 5 5
Iteration 2 1 4 2+4=6 8 13
Iteration 3 2 3 3+3=6 9 22

Return 22.

Example 2: skill = [3,4]

Sorted: [3,4], sum = 7, product = 12. Return 12.

Example 3: skill = [1,1,2,3]

Sorted: [1,1,2,3], first pair 1+3=4, second pair 1+2=3 ≠ 4, return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates; two-pointer pass is O(n)
Space O(1) In-place sorting, constant extra space

The algorithm is efficient for large input sizes up to 10^5 and requires only minimal extra space.

Test Cases

# Provided examples
assert Solution().dividePlayers([3,2,5,1,3,4]) == 22  # multiple teams
assert Solution().dividePlayers([3,4]) == 12  # minimal input
assert Solution().dividePlayers([1,1,2,3]) == -1  # impossible case

# Additional test cases
assert Solution().dividePlayers([1,1,1,1]) == 2  # all same skill
assert Solution().dividePlayers([1,2,3,4,5,6]) == -1  # cannot pair
assert Solution().dividePlayers([1000,1000,1000,1000]) == 1000000  # large numbers
assert Solution().dividePlayers([1,2]) == 2  # minimal valid input
Test Why
[3,2,5,1,3,4] Standard multiple team case
[3,4] Minimal input
[1,1,2,3] Impossible division
[1,1,1,1] All identical skill values
[1,2,3,4,5,6] Unpairable array
[1000,1000,1000,1000] Large values, checks integer overflow
[1,2] Smallest possible valid array

Edge Cases

  1. Minimal input: When skill has only two players, the algorithm correctly computes the chemistry as the product of the two values. Sorting does not change the array, and the sum check is trivial.
  2. All players with identical skills: If every player has the same skill, every pair will naturally have the same sum. The algorithm handles this correctly because the sum check always passes and the chemistry accumulates properly.
  3. Impossible team division: Arrays where no combination of pairs can produce equal team sums (e.g., [1,1,2,3]) are correctly handled because the two-pointer sum check will fail at some point, returning -1. This prevents invalid chemistry sums from being returned.

This solution is robust for all specified constraints and handles extreme values efficiently.