0601MediumArrayHash TableTwo PointersSorting

Balanced Sculling Boats

Tracked in this browser only

Trains the technique from

LeetCode 2491Divide Players Into Teams of Equal Skill

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A rowing club owns two-seat sculling boats and has an even number of rowers on the water. Every rower must be seated in exactly one boat, and every boat must be full.

You are given skill, where skill[i] is the rating of rower i. For a crewed boat, its balance is the total of the two ratings aboard and its drive is the product of those two ratings.

The coach insists that all the boats share the same balance. Return the total drive across every boat when the rowers can be seated that way. When no seating gives every boat the same balance, return -1.

Ratings are at least 1, so a genuine total drive is always positive and can never be confused with the -1 answer.

Examples

Example 1

Input: skill = [3, 4, 6, 5]
Output: 38

Seating 3 with 6 and 4 with 5 gives both boats a balance of 9. Their drives are 18 and 20, so the total drive is 38.

Example 2

Input: skill = [1, 2, 3, 5]
Output: -1

Two boats are needed. The three ways to seat these four rowers give balance pairs of 3 and 8, 4 and 7, then 6 and 5, and no pair is equal, so the answer is -1.

Example 3

Input: skill = [1000, 1, 1, 1000]
Output: 2000

Each boat takes one rating of 1 and one of 1000, so both balances are 1001 and both drives are 1000, for a total of 2000.

Constraints

2 <= skill.length <= 10^5
skill.length is even.
1 <= skill[i] <= 1000
The total drive never exceeds 5 * 10^10, so it fits comfortably in a 64-bit integer.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def divide_players(skill: list[int]) -> int:

Java

public long dividePlayers(int[] skill)

The intended approach

Time O(n log n) for the sort; the inward walk is O(n).Space O(n) for the sorted copy of the ratings.

Sort the ratings. The lowest rating must sit with somebody, and its partner can be no larger than the highest rating, while the highest rating's partner can be no smaller than the lowest, so if a seating exists at all the shared balance is the sum of those two ends. Pair the ends together and step inward: each pair must hit that same balance, otherwise no seating exists. Accumulate the product of each pair as the pairs are formed.

Pythonentry point: divide_players

def divide_players(skill):
    # O(n log n) time from the sort, O(n) space for the sorted copy.
    # Every boat has to reach the same balance, and the weakest rower has to
    # share a boat with someone, so the only balance that can possibly work is
    # the one the weakest and strongest rower produce together. Pairing inward
    # from both ends then either matches that balance every time or fails.
    ordered = sorted(skill)
    target = ordered[0] + ordered[-1]
    total = 0
    low = 0
    high = len(ordered) - 1
    while low < high:
        if ordered[low] + ordered[high] != target:
            return -1
        total += ordered[low] * ordered[high]
        low += 1
        high -= 1
    return total

The obvious version

Search over seatings. Take the first rower still unseated, try each remaining rower as their partner, and recurse on the rest; after the first boat is crewed the balance is fixed, so later boats only accept partners that reproduce it. The first complete seating found supplies the total drive.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_divide_players(skill):
    def solve(rest, target):
        if not rest:
            return 0
        head = rest[0]
        for idx in range(1, len(rest)):
            balance = head + rest[idx]
            if target is not None and balance != target:
                continue
            deeper = solve(rest[1:idx] + rest[idx + 1:], balance)
            if deeper is not None:
                return head * rest[idx] + deeper
        return None

    found = solve(list(skill), None)
    if found is None:
        return -1
    return found

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in