Best Team With No Conflicts — Solution in Python, Java & C++
Best Team With No Conflicts solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Best Team With No Conflicts is a medium coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Sorting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A coach is picking a team for a CodeKairo tournament. Player i has a rating scores[i] and an age ages[i]; the team's score is the sum of its players' scores.
The team must have no conflict: a conflict happens when a younger player has a strictly higher score than an older player. Two players of the same age never conflict.
Return the highest team score the coach can reach.
Example 1
Input: scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Output: 34
Explanation: Scores rise with age, so everyone can play together.
Example 2
Input: scores = [4,5,6,5], ages = [2,1,2,1]
Output: 16
Explanation: Take the last three players: the two 1-year-olds score 5 and 5, and the 2-year-old scores 6. The first player (age 2, score 4) would conflict with the younger players scoring 5.
Example 3
Input: scores = [1,2,3,5], ages = [8,9,10,1]
Output: 6
Explanation: The youngest player (score 5) conflicts with every older player, so take the first three: 1 + 2 + 3 = 6.
Constraints
1 <= scores.length, ages.length <= 1000scores.length == ages.length1 <= scores[i] <= 10^61 <= ages[i] <= 1000
Hints for Best Team With No Conflicts
Hint 1
Sort the players by age, breaking ties by score. In that order, when is a set of players conflict-free?
Hint 2
After sorting, a team is valid exactly when its scores never go down from one chosen player to the next.
Hint 3
So the answer is a maximum-sum non-decreasing subsequence of the sorted scores:
dp[i] = scores[i] + max(dp[j])over earlierjwithscores[j] <= scores[i].
How to solve Best Team With No Conflicts
Sorting by (age, score) turns the pairwise conflict rule into a chain condition: a team is valid if and only if its scores are non-decreasing in that order. The best team is then a maximum-sum non-decreasing subsequence.
Approach
- Sort the players by age, and by score among players of the same age.
- For each player
iin that order, setdp[i]to its score plus the largestdp[j]over earlier playersjwhose score is at mostscores[i](or plus 0 if none). - Return the largest
dp[i].
Why it works
Two chosen players in sorted order either share an age (no conflict, and the tie-break puts the lower score first) or the earlier one is younger, in which case a conflict means exactly that its score is higher. So a set is conflict-free iff its scores never decrease along the sorted order, and the DP enumerates every such chain ending at each player.
Complexity
- Time —
O(n^2) - Space —
O(n)
Pitfalls
- Ties in age must be broken by score: sorting by age alone can put a higher score first and wrongly forbid two same-aged players together.
- The comparison is
<=, not<— equal scores never conflict. - The answer is the maximum over all
dp[i], notdp[n - 1].
Reference solution
Python
from typing import List
def bestTeamScore(scores: List[int], ages: List[int]) -> int:
players = sorted(zip(ages, scores))
dp = []
best = 0
for i, (_, s) in enumerate(players):
top = 0
for j in range(i):
if players[j][1] <= s and dp[j] > top:
top = dp[j]
dp.append(top + s)
best = max(best, top + s)
return bestJava
public static int bestTeamScore(int[] scores, int[] ages) {
int n = scores.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> ages[a] != ages[b] ? ages[a] - ages[b] : scores[a] - scores[b]);
int[] dp = new int[n];
int best = 0;
for (int i = 0; i < n; i++) {
int s = scores[order[i]], top = 0;
for (int j = 0; j < i; j++) if (scores[order[j]] <= s && dp[j] > top) top = dp[j];
dp[i] = top + s;
best = Math.max(best, dp[i]);
}
return best;
}C++
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
int n = scores.size();
vector<pair<int, int>> players(n);
for (int i = 0; i < n; i++) players[i] = {ages[i], scores[i]};
sort(players.begin(), players.end());
vector<int> dp(n, 0);
int best = 0;
for (int i = 0; i < n; i++) {
int s = players[i].second, top = 0;
for (int j = 0; j < i; j++) if (players[j].second <= s && dp[j] > top) top = dp[j];
dp[i] = top + s;
best = max(best, dp[i]);
}
return best;
}JavaScript
var bestTeamScore = function(scores, ages) {
var n = scores.length, order = [];
for (var i = 0; i < n; i++) order.push(i);
order.sort(function(a, b) { return ages[a] !== ages[b] ? ages[a] - ages[b] : scores[a] - scores[b]; });
var dp = [], best = 0;
for (var i = 0; i < n; i++) {
var s = scores[order[i]], top = 0;
for (var j = 0; j < i; j++) if (scores[order[j]] <= s && dp[j] > top) top = dp[j];
dp.push(top + s);
if (top + s > best) best = top + s;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming