LeetCode 1626 - Best Team With No Conflicts

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Sorting

Solution

Problem Understanding

The problem asks us to build a basketball team with the maximum possible total score, while ensuring that the team does not contain any conflicts.

Each player has two attributes:

scores[i], the player's skill score
ages[i], the player's age

A conflict occurs when:

a younger player has a strictly higher score than an older player

This means that if player A is younger than player B, then player A's score must be less than or equal to player B's score. Equal scores are completely valid. Players with the same age can have any score relationship without causing conflicts.

The goal is to choose any subset of players such that:

No conflicts exist
The sum of chosen scores is maximized

The input size is at most 1000, which is large enough that brute force subset enumeration becomes impossible. Since every player can either be selected or skipped, a naive solution would involve checking up to 2^1000 subsets, which is computationally infeasible.

The constraints also reveal an important detail:

Ages are relatively small, up to 1000
Scores can be large, up to 10^6

The moderate input size strongly suggests that an O(n^2) dynamic programming solution is acceptable, because 1000^2 = 1,000,000, which is manageable.

There are several important edge cases to keep in mind:

Multiple players may have the same age. These players never conflict with each other.
Multiple players may have the same score.
A younger player with a higher score invalidates the team.
The optimal team is not necessarily composed of the highest individual scores.
A single player is always a valid team.

For example, a very high scoring young player may prevent adding several older players, reducing the total score overall.

Approaches

Brute Force Approach

The most straightforward solution is to generate every possible subset of players and check whether the subset contains any conflicts.

For each subset:

Compare every pair of selected players
Detect whether a younger player has a strictly higher score
If the subset is valid, compute its total score
Track the maximum total score among all valid subsets

This approach is correct because it explicitly examines every possible team configuration. Therefore, it cannot miss the optimal answer.

However, it is far too slow. With n players, there are 2^n subsets. Even for n = 30, this becomes enormous. Since the actual constraint is 1000, brute force is completely impractical.

Key Insight

The conflict rule becomes much easier to handle if we sort players properly.

Suppose we sort players by:

Age in ascending order
Score in ascending order when ages are equal

After sorting:

Every later player is at least as old as earlier players
We only need to ensure that scores are non-decreasing

This transforms the problem into something very similar to the Longest Increasing Subsequence dynamic programming pattern.

Instead of maximizing sequence length, we maximize total score.

We define:

dp[i] = maximum team score where player i is the last selected player

Then for every earlier player j:

If score[j] <= score[i], player i can safely join the team ending at j
We update:

dp[i] = max(dp[i], dp[j] + score[i])

This works because sorting by age guarantees that no younger player appears after an older player.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n × n^2)	O(n)	Enumerates all subsets and validates conflicts
Optimal Dynamic Programming	O(n^2)	O(n)	Sort players and apply LIS-style DP

Algorithm Walkthrough

Combine each player's age and score into a pair.

This makes sorting easier because each player is represented as a single object containing both attributes. 2. Sort the players by age ascending, then by score ascending.

Sorting by age ensures that later players are never younger than earlier players.

Sorting equal ages by score ensures stable ordering and simplifies the DP condition. 3. Create a DP array.

Let dp[i] represent the maximum achievable team score where player i is included as the last player in the team.

Initially:

dp[i] = score of player i

because every player alone forms a valid team. 4. Iterate through every player i.

For each player, examine all previous players j. 5. Check whether player i can extend the team ending at j.

Since ages are already sorted, the only remaining condition is:

score[j] <= score[i]

If true, adding player i does not create conflicts. 6. Update the DP value.

If player i can extend player j's team:

dp[i] = max(dp[i], dp[j] + score[i])

Track the global maximum.

The answer is the largest value in the DP array.

Why it works

Sorting guarantees that player ages never decrease as we move forward. Therefore, conflicts can only occur if scores decrease.

The DP transition only allows extending teams where the previous score is less than or equal to the current score. This maintains the invariant that no younger player has a strictly higher score than an older player.

Because every valid extension is considered, the algorithm explores all valid team constructions and finds the maximum total score.

Python Solution

from typing import List

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        players = sorted(zip(ages, scores))

        n = len(players)
        dp = [0] * n

        best = 0

        for i in range(n):
            current_score = players[i][1]

            dp[i] = current_score

            for j in range(i):
                previous_score = players[j][1]

                if previous_score <= current_score:
                    dp[i] = max(dp[i], dp[j] + current_score)

            best = max(best, dp[i])

        return best

The implementation begins by combining ages and scores using zip, then sorting the resulting pairs. Python's tuple sorting automatically sorts by the first value and then the second value, which perfectly matches the required ordering.

The DP array stores the best possible team score ending at each player. Every player initially forms a valid team by themselves, so dp[i] starts as the player's own score.

The nested loop checks all earlier players. Because the players are sorted by age, we only need to verify the score condition. If the previous player's score is less than or equal to the current player's score, then the current player can safely extend that team.

The variable best continuously tracks the largest valid team score discovered during processing.

Go Solution

package main

import "sort"

func bestTeamScore(scores []int, ages []int) int {
	n := len(scores)

	type Player struct {
		age   int
		score int
	}

	players := make([]Player, n)

	for i := 0; i < n; i++ {
		players[i] = Player{
			age:   ages[i],
			score: scores[i],
		}
	}

	sort.Slice(players, func(i, j int) bool {
		if players[i].age == players[j].age {
			return players[i].score < players[j].score
		}
		return players[i].age < players[j].age
	})

	dp := make([]int, n)

	best := 0

	for i := 0; i < n; i++ {
		dp[i] = players[i].score

		for j := 0; j < i; j++ {
			if players[j].score <= players[i].score {
				if dp[j]+players[i].score > dp[i] {
					dp[i] = dp[j] + players[i].score
				}
			}
		}

		if dp[i] > best {
			best = dp[i]
		}
	}

	return best
}

The Go implementation follows the exact same logic as the Python version.

Since Go does not have built in tuple sorting like Python, we define a Player struct containing age and score. We then use sort.Slice with a custom comparator.

The DP logic is identical. Go slices are dynamically sized and work similarly to arrays for indexed access.

Integer overflow is not an issue because the maximum total score is at most:

1000 × 10^6 = 10^9

which safely fits inside Go's int on standard LeetCode environments.

Worked Examples

Example 1

scores = [1,3,5,10,15]
ages   = [1,2,3,4,5]

After sorting:

Index	Age	Score
0	1	1
1	2	3
2	3	5
3	4	10
4	5	15

DP progression:

i	Current Score	Valid Previous Players	dp[i]
0	1	none	1
1	3	1	4
2	5	1, 3	9
3	10	1, 3, 5	19
4	15	1, 3, 5, 10	34

Final answer:

Example 2

scores = [4,5,6,5]
ages   = [2,1,2,1]

After sorting:

Index	Age	Score
0	1	5
1	1	5
2	2	4
3	2	6

DP progression:

i	Current Score	Valid Previous Players	dp[i]
0	5	none	5
1	5	5	10
2	4	none	4
3	6	5, 5, 4	16

Final answer:

Example 3

scores = [1,2,3,5]
ages   = [8,9,10,1]

After sorting:

Index	Age	Score
0	1	5
1	8	1
2	9	2
3	10	3

DP progression:

i	Current Score	Valid Previous Players	dp[i]
0	5	none	5
1	1	none	1
2	2	1	3
3	3	1, 2	6

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Nested loops compare each pair of players once
Space	O(n)	DP array stores one value per player

The sorting step costs O(n log n), but the dynamic programming portion costs O(n^2), which dominates overall complexity.

The space usage is linear because the algorithm only stores the sorted players and the DP array.

Test Cases

# Provided example 1
assert Solution().bestTeamScore(
    [1, 3, 5, 10, 15],
    [1, 2, 3, 4, 5]
) == 34

# Provided example 2
assert Solution().bestTeamScore(
    [4, 5, 6, 5],
    [2, 1, 2, 1]
) == 16

# Provided example 3
assert Solution().bestTeamScore(
    [1, 2, 3, 5],
    [8, 9, 10, 1]
) == 6

# Single player
assert Solution().bestTeamScore(
    [10],
    [5]
) == 10

# All same age, no conflicts possible
assert Solution().bestTeamScore(
    [1, 2, 3, 4],
    [5, 5, 5, 5]
) == 10

# Strictly decreasing scores with increasing ages
assert Solution().bestTeamScore(
    [10, 9, 8, 7],
    [1, 2, 3, 4]
) == 10

# Equal scores across different ages
assert Solution().bestTeamScore(
    [5, 5, 5],
    [1, 2, 3]
) == 15

# Complex mixed case
assert Solution().bestTeamScore(
    [9, 2, 8, 8, 2],
    [4, 1, 3, 3, 5]
) == 27

# Multiple valid combinations
assert Solution().bestTeamScore(
    [6, 5, 4, 3],
    [2, 1, 2, 1]
) == 16

# Large scores
assert Solution().bestTeamScore(
    [1000000, 1000000],
    [1, 2]
) == 2000000

Test Summary

Test	Why
Increasing ages and scores	Verifies all players can be selected
Mixed ages with conflicts	Tests conflict filtering
Young high scorer	Verifies invalid combinations are excluded
Single player	Smallest valid input
All same age	Confirms same-age players never conflict
Decreasing scores	Ensures algorithm rejects conflicting chains
Equal scores	Confirms equal scores are valid
Complex mixed case	Tests non-trivial DP transitions
Multiple valid subsets	Verifies maximum sum selection
Large score values	Confirms large integers are handled correctly

Edge Cases

One important edge case occurs when all players have the same age. Since conflicts only happen between younger and older players, equal ages never create conflicts. A buggy implementation might incorrectly enforce score ordering even among same-age players. Sorting by both age and score, combined with the DP condition, naturally handles this correctly.

Another important edge case is strictly decreasing scores with increasing ages. In this situation, selecting multiple players would always create conflicts because younger players would have higher scores than older players. The algorithm correctly avoids extending invalid sequences because the DP transition only allows non-decreasing scores.

A third critical edge case involves duplicate scores. Equal scores are allowed even when ages differ because conflicts require a strictly higher score. Using the condition <= instead of < is essential. If the implementation used a strict inequality, it would incorrectly reject many valid teams.

A final edge case is a single player input. Since any individual player forms a valid team, the algorithm initializes each DP entry with the player's own score. This guarantees correct behavior even when no valid extensions exist.