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
- Sort the array. The target total is then forced: it must be
skill[0] + skill[-1], pairing the weakest with the strongest. - Use two pointers from the ends: if any pair's sum differs from the target, return
-1. - Otherwise accumulate the product of each pair.
- 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 isskill[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.