I like to read this solution as a small machine: keep the useful information, throw away the noise. For 1626. Best Team With No Conflicts, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming, backtracking.
The notes already sitting in the source point us in the right direction:
- backtrack
- TLE
- 49 / 147 test cases passed.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are check, backtrack, bestTeamScore, players.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//backtrack
02//TLE
03//49 / 147 test cases passed.
04class Solution {
05public:
06 int n;
07 int ans;
08
09 bool check(vector<int>& scores, vector<int>& ages, vector<int>& chosen, int cur){
10 for(const int& p : chosen){
11 if(ages[cur] < ages[p] && scores[cur] > scores[p])
12 return false;
13 if(ages[cur] > ages[p] && scores[cur] < scores[p])
14 return false;
15 }
16
17 return true;
18 }
19
20 void backtrack(vector<int>& scores, vector<int>& ages, vector<int>& chosen, int cur, int score){
21 if(cur == n){
22 ans = max(ans, score);
23 }else{
24 //not choose cur
25 backtrack(scores, ages, chosen, cur+1, score);
26
27 //choose cur
28 if(check(scores, ages, chosen, cur)){
29 chosen.push_back(cur);
30 backtrack(scores, ages, chosen, cur+1, score+scores[cur]);
31 chosen.pop_back();
32 }
33 }
34 }
35
36 int bestTeamScore(vector<int>& scores, vector<int>& ages) {
37 n = scores.size();
38
39 vector<int> chosen;
40 backtrack(scores, ages, chosen, 0, 0);
41
42 return ans;
43 }
44};
45
46//sort + backtrack
47//TLE
48//52 / 147 test cases passed.
49//how to do memorization? There are at most 1000 players, hard to use bitmask as state!
50class Solution {
51public:
52 int max_score;
53
54 void backtrack(vector<int>& scores, vector<int>& ages, vector<int>& players, int pi, vector<int>& chosen){
55 if(pi == players.size()){
56 int cur_score = 0;
57 for(const int& p : chosen){
58 // cout << scores[p] << " ";
59 cur_score += scores[p];
60 }
61 // cout << endl;
62 max_score = max(max_score, cur_score);
63 }else{
64 //not choose cur
65 backtrack(scores, ages, players, pi+1, chosen);
66
67 int p = players[pi];
68 /*
69 sort scores ascending so
70 the last player in its age's group will have max score,
71 here we compare current player's score with last chosen player's score,
72 and we know that last chosen player's score is the highest in its age
73 */
74 //actually we don't need to check age!
75 if(chosen.empty() ||
76 !(/*ages[p] > ages[chosen.back()] && */ scores[p] < scores[chosen.back()])){
77 //choose cur
78 chosen.push_back(p);
79 backtrack(scores, ages, players, pi+1, chosen);
80 chosen.pop_back();
81 }
82 }
83 }
84
85 int bestTeamScore(vector<int>& scores, vector<int>& ages) {
86 int n = scores.size();
87 vector<int> players(n);
88 iota(players.begin(), players.end(), 0);
89
90 //ascending by age, ascending by score
91 sort(players.begin(), players.end(), [&](int& pi1, int& pi2){
92 return (ages[pi1] == ages[pi2]) ? scores[pi1] < scores[pi2] : ages[pi1] < ages[pi2];
93 });
94
95 max_score = 0;
96
97 vector<int> chosen;
98 backtrack(scores, ages, players, 0, chosen);
99
100 return max_score;
101 }
102};
103
104//simplify backtrack argument: use two int instead of a vector
105//TLE
106//60 / 147 test cases passed.
107class Solution {
108public:
109 int max_score;
110
111 void backtrack(vector<int>& scores, vector<int>& ages, vector<int>& players, int pi, int last_chosen, int cur_score){
112 if(pi == players.size()){
113 max_score = max(max_score, cur_score);
114 }else{
115 //not choose cur
116 backtrack(scores, ages, players, pi+1, last_chosen, cur_score);
117
118 int p = players[pi];
119 /*
120 sort scores ascending so
121 the last player in its age's group will have max score,
122 here we compare current player's score with last chosen player's score,
123 and we know that last chosen player's score is the highest in its age
124 */
125 if(last_chosen == -1 ||
126 !(/*ages[p] > ages[chosen.back()] && */scores[p] < scores[last_chosen])){
127 //choose cur
128 backtrack(scores, ages, players, pi+1, p, cur_score+scores[p]);
129 }
130 }
131 }
132
133 int bestTeamScore(vector<int>& scores, vector<int>& ages) {
134 int n = scores.size();
135 vector<int> players(n);
136 iota(players.begin(), players.end(), 0);
137
138 //ascending by age, ascending by score
139 sort(players.begin(), players.end(), [&](int& pi1, int& pi2){
140 return (ages[pi1] == ages[pi2]) ? scores[pi1] < scores[pi2] : ages[pi1] < ages[pi2];
141 });
142
143 max_score = 0;
144
145 backtrack(scores, ages, players, 0, -1, 0);
146
147 return max_score;
148 }
149};
150
151//a trial of using memorization, slower than previous?
152//TLE
153//44 / 147 test cases passed.
154class Solution {
155public:
156 vector<vector<unordered_map<int, int>>> memo;
157
158 int backtrack(vector<int>& scores, vector<int>& ages, vector<int>& players, int pi, int last_chosen, int cur_score){
159 if(memo[pi+1][last_chosen+1].find(cur_score) != memo[pi+1][last_chosen+1].end()){
160 return memo[pi+1][last_chosen+1][cur_score];
161 }else if(pi == players.size()){
162 return memo[pi+1][last_chosen+1][cur_score] = cur_score;
163 }else{
164 int res = 0;
165
166 //not choose cur
167 res = backtrack(scores, ages, players, pi+1, last_chosen, cur_score);
168
169 int p = players[pi];
170
171 //don't need to check age!
172 if(last_chosen == -1 ||
173 !(/*ages[p] > ages[chosen.back()] && */scores[p] < scores[last_chosen])){
174 //choose cur
175 res = max(res, backtrack(scores, ages, players, pi+1, p, cur_score+scores[p]));
176 }
177
178 return memo[pi+1][last_chosen+1][cur_score] = res;
179 }
180 }
181
182 int bestTeamScore(vector<int>& scores, vector<int>& ages) {
183 int n = scores.size();
184 vector<int> players(n);
185 iota(players.begin(), players.end(), 0);
186
187 sort(players.begin(), players.end(), [&](int& pi1, int& pi2){
188 return (ages[pi1] == ages[pi2]) ? scores[pi1] < scores[pi2] : ages[pi1] < ages[pi2];
189 });
190
191 memo = vector<vector<unordered_map<int, int>>>(n+2,
192 vector<unordered_map<int, int>>(n+2));
193
194 return backtrack(scores, ages, players, 0, -1, 0);
195 }
196};
197
198//1D DP
199//each cell means the optimal can be got using the previous i players
200//https://leetcode.com/problems/best-team-with-no-conflicts/discuss/899475/Fairly-easy-DP
201//Runtime: 232 ms, faster than 51.78% of C++ online submissions for Best Team With No Conflicts.
202//Memory Usage: 19.2 MB, less than 5.33% of C++ online submissions for Best Team With No Conflicts.
203class Solution {
204public:
205 int bestTeamScore(vector<int>& scores, vector<int>& ages) {
206 int n = scores.size();
207
208 vector<int> players(n);
209 iota(players.begin(), players.end(), 0);
210
211 //sort
212 sort(players.begin(), players.end(),
213 [&](int& p1, int& p2){
214 return (ages[p1] == ages[p2]) ? (scores[p1] < scores[p2]) : (ages[p1] < ages[p2]);
215 });
216
217 vector<int> dp(n);
218 //the actual index
219 int pi, pj;
220
221 //visit the players, the younger the earlier to be visited
222 for(int i = 0; i < n; ++i){
223 //map to the actual index
224 pi = players[i];
225 dp[i] = scores[pi];
226
227 //visit players younger than pi
228 for(int j = 0; j < i; ++j){
229 pj = players[j];
230 if(scores[pj] <= scores[pi]){
231 //dp[i]: the optimal score can be got formed of players of younger than or equal to pi
232 dp[i] = max(dp[i], dp[j]+scores[pi]);
233 }
234 }
235 }
236
237 return *max_element(dp.begin(), dp.end());
238 }
239};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.