Best Team With No Conflicts: Sorting Meets LIS-Style DP

You are the manager of a basketball team. You have a list of players, each with a score and an age. You want to pick a team that maximizes the total score, but there is a rule: a younger player must not have a strictly higher score than an older player on the same team. If that happens, it creates a conflict.

This is LeetCode 1626: Best Team With No Conflicts. Given two arrays scores and ages, find the highest total score of all possible teams with no conflicts. Players of the same age never conflict with each other.

Why this problem matters

This problem is a disguised variant of the Longest Increasing Subsequence pattern. Instead of finding the longest subsequence, you are finding the maximum sum subsequence where a certain ordering property holds. The key insight is that sorting transforms the conflict rule into a simple condition you can check with a nested loop.

Once you see the connection to LIS, the entire solution clicks into place. The same "sort, then DP over predecessors" strategy shows up in problems like Russian Doll Envelopes, Longest String Chain, and Number of Longest Increasing Subsequences. Mastering it here gives you a reusable building block for all of them.

The approach

The conflict rule says: if player A is younger than player B, then player A must not have a strictly higher score. Equivalently, if we sort players by age (and break ties by score), a valid team is one where the scores form a non-decreasing subsequence.

That transforms the problem into: sort by (age, score), then find the maximum sum subsequence where scores are non-decreasing. This is exactly the LIS-style DP pattern, but instead of counting length, you sum scores.

Here is the algorithm:

1. Pair each player as (age, score) and sort by age first, then by score.
2. Create a dp array where dp[i] is the maximum total score of a valid team ending with player i.
3. Initialize dp[i] = scores[i] (each player alone is a valid team).
4. For each player i, scan all previous players j. If scores[j] is not greater than scores[i], you can extend the team ending at j by adding player i.
5. The answer is max(dp).

def best_team_score(scores, ages):
    players = sorted(zip(ages, scores))
    n = len(players)
    dp = [0] * n

    for i in range(n):
        dp[i] = players[i][1]
        for j in range(i):
            if players[j][1] <= players[i][1]:
                dp[i] = max(dp[i], dp[j] + players[i][1])

    return max(dp)

Step-by-step walkthrough

Let's trace through the example scores = [1, 2, 3, 5], ages = [8, 9, 10, 1]. After sorting by (age, score), the players become: (1,5), (8,1), (9,2), (10,3).

Player 0 (age 1, score 5) is a strong individual player, but including them with any of the older, lower-scoring players creates a conflict. The best team turns out to be players (8,1), (9,2), (10,3), with scores forming the non-decreasing sequence [1, 2, 3] and a total of 6.

Notice how the DP is identical in structure to LIS. The only differences are: (1) you sort by a secondary key first, and (2) you sum values instead of counting length. The inner loop still scans all predecessors and picks the best compatible one.

Complexity analysis

The brute force approach considers every possible team (every subset of players), checks for conflicts, and tracks the maximum score. With n players, that is 2^n subsets.

The sort + DP approach sorts in O(n log n), then runs the nested DP loop in O(n^2). The DP dominates, giving O(n^2) overall. Space is O(n) for the sorted pairs and the dp array.

Edge cases to watch for

• All players same age: no conflicts are possible since same-age players never conflict. The answer is the sum of all scores.
• Single player: return that player's score. A team of one is always valid.
• All scores equal: no conflicts possible regardless of age. The answer is the sum of all scores.
• Scores strictly decreasing with increasing age: e.g., ages [1,2,3], scores [10,5,1]. Every pair conflicts. The answer is max(scores), since you can only pick one player.
• Already sorted by both age and score: the entire roster is a valid team. The answer is the sum of all scores.
• Duplicate (age, score) pairs: same age never conflicts, so identical players can always be on the same team. The sort-and-compare logic handles this naturally since scores[j] will equal scores[i], satisfying the non-decreasing condition.

The building blocks

This problem combines two reusable patterns.

The first is sorting to simplify constraints. The conflict rule involves two dimensions (age and score), and checking it directly across arbitrary pairs is messy. Sorting by age (with score as a tiebreaker) collapses the problem to a single dimension. After sorting, you only need to check whether scores are non-decreasing, and you only need to look at earlier elements in the sorted order. This "sort to reduce dimensions" strategy is the same idea behind the Longest Increasing Subsequence binary search approach and the Russian Doll Envelopes problem.

The second is LIS-style DP with variable lookback. The transition dp[i] = max(dp[j] + score[i]) for all valid j < i is the same scan-back pattern from LIS. Each position looks at every predecessor and picks the best one that satisfies the compatibility condition. In LIS, the condition is "strictly less than." Here, it is "less than or equal to." The shape of the DP is identical. You define dp[i] as the best answer ending at index i, scan all earlier indices, check the condition, and take the max.

Once you recognize "sort, then run LIS-style DP" as a single reusable block, you can apply it to any problem where a multi-dimensional constraint can be reduced to a single-dimension ordering check.

From understanding to recall

You have just walked through the full solution: sort by (age, score), run LIS-style DP summing scores instead of counting length. The logic is clean and the connection to LIS is direct. But reading through a solution and writing it from scratch under pressure are very different skills.

In an interview, you need to independently see that sorting collapses the two-dimensional conflict rule into a one-dimensional check. You need to write the nested DP loop without hesitation and remember that dp[i] stores a sum, not a length. These details slip away without practice.

Spaced repetition is the most effective way to lock in this pattern. You revisit the problem at increasing intervals, write the sort + DP solution from memory, and each time the pattern becomes more automatic. After a few reps, you will recognize the "sort to reduce dimensions, then LIS-style DP" template instantly whenever it appears, whether the problem is about basketball teams, envelopes, or string chains.

Related posts

• Longest Increasing Subsequence
• House Robber
• Coin Change