1900. The Earliest and Latest Rounds Where Players Compete LeetCode Solution
In this guide, you will get 1900. The Earliest and Latest Rounds Where Players Compete LeetCode Solution with the best time and space complexity. The solution to The Earliest and Latest Rounds Where Players Compete problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of The Earliest and Latest Rounds Where Players Compete
There is a tournament where n players are participating. The players are standing in a single row and are numbered from 1 to n based on their initial standing position (player 1 is the first player in the row, player 2 is the second player in the row, etc.).
The tournament consists of multiple rounds (starting from round number 1). In each round, the ith player from the front of the row competes against the ith player from the end of the row, and the winner advances to the next round. When the number of players is odd for the current round, the player in the middle automatically advances to the next round.
For example, if the row consists of players 1, 2, 4, 6, 7
Player 1 competes against player 7.
Player 2 competes against player 6.
Player 4 automatically advances to the next round.
After each round is over, the winners are lined back up in the row based on the original ordering assigned to them initially (ascending order).
The players numbered firstPlayer and secondPlayer are the best in the tournament. They can win against any other player before they compete against each other. If any two other players compete against each other, either of them might win, and thus you may choose the outcome of this round.
Given the integers n, firstPlayer, and secondPlayer, return an integer array containing two values, the earliest possible round number and the latest possible round number in which these two players will compete against each other, respectively.
Example 1:
Input: n = 11, firstPlayer = 2, secondPlayer = 4
Output: [3,4]
Explanation:
One possible scenario which leads to the earliest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 2, 3, 4, 5, 6, 11
Third round: 2, 3, 4
One possible scenario which leads to the latest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 1, 2, 3, 4, 5, 6
Third round: 1, 2, 4
Fourth round: 2, 4
Example 2:
Input: n = 5, firstPlayer = 1, secondPlayer = 5
Output: [1,1]
Explanation: The players numbered 1 and 5 compete in the first round.
There is no way to make them compete in any other round.
Constraints:
2 <= n <= 28
1 <= firstPlayer < secondPlayer <= n
Complexity Analysis
Time Complexity: O(n^4)
Space Complexity: O(n^2)
1900. The Earliest and Latest Rounds Where Players Compete LeetCode Solution in C++
class Solution {
public:
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
using P = pair<int, int>;
vector<vector<vector<P>>> mem(n + 1,
vector<vector<P>>(n + 1, vector<P>(n + 1)));
const auto [a, b] = solve(firstPlayer, n - secondPlayer + 1, n, mem);
return {a, b};
}
private:
// Returns the (earliest, latest) pair, the first player is the l-th player
// from the front, the second player is the r-th player from the end, and
// there're k people.
pair<int, int> solve(int l, int r, int k,
vector<vector<vector<pair<int, int>>>>& mem) {
if (l == r)
return {1, 1};
if (l > r)
swap(l, r);
if (mem[l][r][k] != pair<int, int>{0, 0})
return mem[l][r][k];
int a = INT_MAX;
int b = INT_MIN;
// Enumerate all the possible positions.
for (int i = 1; i <= l; ++i)
for (int j = l - i + 1; j <= r - i; ++j) {
if (i + j > (k + 1) / 2 || i + j < l + r - k / 2)
continue;
const auto [x, y] = solve(i, j, (k + 1) / 2, mem);
a = min(a, x + 1);
b = max(b, y + 1);
}
return mem[l][r][k] = {a, b};
}
}; /* code provided by PROGIEZ */
1900. The Earliest and Latest Rounds Where Players Compete LeetCode Solution in Java
class Solution {
public int[] earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
int[][][][] mem = new int[n + 1][n + 1][n + 1][2];
return solve(firstPlayer, n - secondPlayer + 1, n, mem);
}
// Returns the (earliest, latest) pair, the first player is the l-th player
// from the front, the second player is the r-th player from the end, and
// there're k people.
private int[] solve(int l, int r, int k, int[][][][] mem) {
if (l == r)
return new int[] {1, 1};
if (l > r)
return solve(r, l, k, mem);
if (!Arrays.equals(mem[l][r][k], new int[] {0, 0}))
return mem[l][r][k];
int a = Integer.MAX_VALUE;
int b = Integer.MIN_VALUE;
// Enumerate all the possible positions.
for (int i = 1; i <= l; ++i)
for (int j = l - i + 1; j <= r - i; ++j) {
if (i + j > (k + 1) / 2 || i + j < l + r - k / 2)
continue;
int[] res = solve(i, j, (k + 1) / 2, mem);
a = Math.min(a, res[0] + 1);
b = Math.max(b, res[1] + 1);
}
return mem[l][r][k] = new int[] {a, b};
}
} // code provided by PROGIEZ
1900. The Earliest and Latest Rounds Where Players Compete LeetCode Solution in Python
class Solution:
def earliestAndLatest(self, n: int,
firstPlayer: int, secondPlayer: int) -> list[int]:
@functools.lru_cache(None)
def dp(l: int, r: int, k: int) -> list[int]:
"""
Returns the (earliest, latest) pair, the first player is the l-th player
from the front, the second player is the r-th player from the end, and
there're k people.
"""
if l == r:
return [1, 1]
if l > r:
return dp(r, l, k)
a = math.inf
b = -math.inf
# Enumerate all the possible positions.
for i in range(1, l + 1):
for j in range(l - i + 1, r - i + 1):
if not l + r - k // 2 <= i + j <= (k + 1) // 2:
continue
x, y = dp(i, j, (k + 1) // 2)
a = min(a, x + 1)
b = max(b, y + 1)
return [a, b]
return dp(firstPlayer, n - secondPlayer + 1, n) # code by PROGIEZ
