Editorial: LeetCode 1900 the Earliest and Latest Rounds Where Players Compete
https://leetcode.com/problems/the-earliest-and-latest-rounds-where-players-compete/ from Google
Thinking process:
In this problem, we basically need to simulate the tournament. We can use a recursive funtion to simulate this tournament. In this function, we need two arrays, players as the current players and winners as the result of the winners, who will be joining the next round.
With this setup, we also need a left pointer and a right pointer to mean the current player index. If the left player is the firstPlayer and the right player is the secondPlayer, we know that we find a round. We update our min round and max round with this round.
1if (players[left] == fp and players[right] == sp) {
2 r1 = min(r1, rounds);
3 r2 = max(r2, rounds);
4 return;
5}
If only one of them are the firstPlayer or secondPlayer, we know they must win and proceed to next round.
1if (players[left] == fp or players[left] == sp) {
2 winners.push_back(players[left]);
3 dfs(players, winners, left+1, right-1, fp, sp, rounds);
4} else if (players[right] == sp or players[right] == fp) {
5 winners.push_back(players[right]);
6 dfs(players, winners, left+1, right-1, fp, sp, rounds);
7}
If non of them are the firstPlayer or secondPlayer, we try two possible results with recursion.
1winners.push_back(players[left]);
2dfs(players, winners, left+1, right-1, fp, sp, rounds);
3winners.pop_back();
4winners.push_back(players[right]);
5dfs(players, winners, left+1, right-1, fp, sp, rounds);
Finally, if left index is greater or equal to right index, we proceed to next round, so we use the winners as the players next round and an empty array as the winners. We also need to sort the winners as we need to maintain their original order.
1if (left >= right) {
2 if (left == right) winners.push_back(players[left]);
3 sort(winners.begin(), winners.end());
4 dfs(winners, vector<int>(), 0, (int)winners.size()-1, fp, sp, rounds+1);
5 return;
6}
In my code you can see that I use vector<int> players to be the parameter. There will be a copy in each recursive call and thus I can only pass 118 / 136 test cases. Even if we change to reference like vector<int>& players, I still can’t pass all test cases because of TLE.
Since the number of players is at most 28, we can actually use a bit map to represent the current players, which will make this more efficient as we don’t have the array copy operation. I’ll still post the TLE code here as it’s more straitforward and generalized, but you can find the bit map code in the discussion section in the Leetcode link.
Here is the code.
1class Solution {
2public:
3 int r1 = INT_MAX;
4 int r2 = INT_MIN;
5 void dfs(vector<int> players, vector<int> winners, int left, int right, int fp, int sp, int rounds) {
6 if (left >= right) {
7 if (left == right) winners.push_back(players[left]);
8 sort(winners.begin(), winners.end());
9 dfs(winners, vector<int>(), 0, (int)winners.size()-1, fp, sp, rounds+1);
10 return;
11 }
12 if (players[left] == fp and players[right] == sp) {
13 r1 = min(r1, rounds);
14 r2 = max(r2, rounds);
15 return;
16 }
17 if (players[left] == fp or players[left] == sp) {
18 winners.push_back(players[left]);
19 dfs(players, winners, left+1, right-1, fp, sp, rounds);
20 } else if (players[right] == sp or players[right] == fp) {
21 winners.push_back(players[right]);
22 dfs(players, winners, left+1, right-1, fp, sp, rounds);
23 } else {
24 winners.push_back(players[left]);
25 dfs(players, winners, left+1, right-1, fp, sp, rounds);
26 winners.pop_back();
27 winners.push_back(players[right]);
28 dfs(players, winners, left+1, right-1, fp, sp, rounds);
29 }
30 }
31 vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
32 vector<int> players;
33 vector<int> winners;
34 for (int i=1; i<=n; i++) players.push_back(i);
35 dfs(players, winners, 0, n-1, firstPlayer, secondPlayer, 1);
36 return {r1, r2};
37 }
38};