⚡Flashcard Drill➔
NeetCode #206LC-2491MediumTwo Pointers
← Back to All Problems

#206 · #2491 · Divide Players Into Teams of Equal Skill(划分技能点相等的团队)

📌 Problem Statement & Constraints

You are given an array skill of even length where skill[i] is the skill of player i. Divide the players into teams of 2 such that every team has the same total skill. Return the sum of the products of the skills in each team, or -1 if impossible. Constraints: 2 <= skill.length <= 10^5, skill.length is even, 1 <= skill[i] <= 1000.

💡 Core Algorithmic Approaches

  1. Sort the array. The target total is then forced: it must be skill[0] + skill[-1], pairing the weakest with the strongest.
  2. Use two pointers from the ends: if any pair's sum differs from the target, return -1.
  3. Otherwise accumulate the product of each pair.
  4. The greedy pairing is forced, not chosen: the weakest player can only be paired with the strongest to reach the target, which pins down the entire matching.

💻 Benchmark Python3 Implementation

class Solution:
    def dividePlayers(self, skill: List[int]) -> int:
        skill.sort()
        i, j = 0, len(skill) - 1
        target = skill[0] + skill[-1]     # forced team total
        res = 0
        while i < j:
            if skill[i] + skill[j] != target:
                return -1                 # team totals differ
            res += skill[i] * skill[j]
            i += 1
            j -= 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates; the pairing scan is O(n).
💾 Space Complexity
O(1) beyond the sort.

⚠️ Interview Pitfalls & Follow-ups

  • Trying all pairings: factorial, and unnecessary -- the pairing is forced once the target is fixed.
  • Computing the target as 2 * average: it is skill[0] + skill[-1] after sorting, which avoids any division or rounding concerns.
  • Returning 0 instead of -1 when a pair mismatches: the failure sentinel is -1.
  • Assuming the target can be chosen freely: it is determined by the extreme pair, since the weakest player must be in some team.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems