The Earliest and Latest Rounds Where Players Compete Solution
The Earliest and Latest Rounds Where Players Compete solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
The Earliest and Latest Rounds Where Players Compete is a hard coding problem on dynamic programming and memoization, asked in Google interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Memoization
- Asked at: 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
n players stand in a row, numbered 1 to n by their position, for a knockout tournament. In every round, the i-th player from the front plays the i-th player from the back, and the winner advances. If the number of players in a round is odd, the player in the middle advances automatically.
After a round, the winners line up again in their original relative order (by their starting numbers), and the next round begins.
Players firstPlayer and secondPlayer are the strongest: each beats any other opponent. Every other match may go either way — you choose. Return [earliest, latest]: the earliest and the latest round numbers (counting from 1) in which firstPlayer and secondPlayer can meet.
Example 1
Input: n = 11, firstPlayer = 2, secondPlayer = 4
Output: [3,4]
Explanation: Earliest: round 1 can leave 2,3,4,5,6,11, round 2 can leave 2,3,4, and then 2 faces 4 in round 3. Latest: the results can also keep them apart until round 4.
Example 2
Input: n = 5, firstPlayer = 1, secondPlayer = 5
Output: [1,1]
Explanation: Players 1 and 5 face each other in the very first round.
Example 3
Input: n = 4, firstPlayer = 1, secondPlayer = 3
Output: [2,2]
Explanation: Round 1 pairs 1–4 and 2–3, so both stars win and meet in round 2.
Constraints
2 <= n <= 281 <= firstPlayer < secondPlayer <= n
Hints for The Earliest and Latest Rounds Where Players Compete
Hint 1
Only three numbers matter for the rest of the tournament: how many players are left and the positions of the two stars. Memoise on
(n, first, second).Hint 2
The tournament is symmetric: mirroring the row (position
pbecomesn + 1 - p) does not change the answer, so you may assume the stars are closer to the front,first + second <= n + 1.Hint 3
Instead of enumerating every match result, count how many winners land before the first star (
i) and between the stars (j): those two numbers decide the stars' new positions. Careful with the case where the second star is in the back half — the players between its opponent and itself contribute a fixed number of winners.
How to solve The Earliest and Latest Rounds Where Players Compete
The future depends only on the number of players left and the two stars' positions, so a memoised search on (n, f, s) works. Within a round, the stars' next positions are determined by how many winners precede each of them, which can be enumerated directly instead of trying all 2^(n/2) match outcomes.
Approach
- If
f + s == n + 1, the stars meet now: return[1, 1]. - If
f + s > n + 1, mirror:(f, s) = (n + 1 - s, n + 1 - f). Letnxt = (n + 1) / 2be the next round's size. - If
s <= nxt(both in the front half): foriin[0, f - 1]winners beforefandjin[0, s - f - 1]winners between them, recurse on(nxt, i + 1, i + j + 2). - Otherwise
sis in the back half and playss' = n + 1 - s(withf < s'). Then - 2s'players strictly betweens'andsalways contributemid = (n - 2s' + 1) / 2winners. Foriin[0, f - 1]andjin[0, s' - f - 1], recurse on(nxt, i + 1, i + j + mid + 2). - Return 1 plus the minimum and 1 plus the maximum of the recursive answers.
Why it works
Every match pairs position p with n + 1 - p. A match in front of the first star (p < f) has its other player behind both stars, so it adds a winner before f exactly when the front player wins — any count from 0 to f - 1 is possible, and which matches are won does not matter. The same reasoning applies between the stars. Players between s' and s pair among themselves (plus the middle player), so they always add the same number of winners before s. That enumerates every reachable pair of next positions.
Complexity
- Time —
O(n^5) in the worst case, tiny for n ≤ 28 - Space —
O(n^3)
Pitfalls
- Winners keep their original relative order — a winner from the back half does not take its opponent's place.
- The middle player of an odd round advances automatically and must be counted when it sits between the stars.
- Rounds are counted from 1, so meeting immediately is
[1, 1].
Reference solution
Python
from typing import List
from functools import lru_cache
def earliestAndLatest(n: int, firstPlayer: int, secondPlayer: int) -> List[int]:
@lru_cache(maxsize=None)
def dfs(n, f, s):
if f + s == n + 1:
return (1, 1)
if f + s > n + 1:
f, s = n + 1 - s, n + 1 - f
nxt = (n + 1) // 2
lo, hi = 100, 0
if s <= nxt:
for i in range(f):
for j in range(s - f):
a, b = dfs(nxt, i + 1, i + j + 2)
lo = min(lo, a)
hi = max(hi, b)
else:
sp = n + 1 - s
mid = (n - 2 * sp + 1) // 2
for i in range(f):
for j in range(sp - f):
a, b = dfs(nxt, i + 1, i + j + mid + 2)
lo = min(lo, a)
hi = max(hi, b)
return (lo + 1, hi + 1)
return list(dfs(n, firstPlayer, secondPlayer))Java
static int[][][][] tourMemo = new int[29][29][29][];
static int[] tourDfs(int n, int f, int s) {
if (f + s == n + 1) return new int[] {1, 1};
if (f + s > n + 1) { int t = f; f = n + 1 - s; s = n + 1 - t; }
if (tourMemo[n][f][s] != null) return tourMemo[n][f][s];
int nxt = (n + 1) / 2, lo = 100, hi = 0;
if (s <= nxt) {
for (int i = 0; i < f; i++) for (int j = 0; j < s - f; j++) {
int[] r = tourDfs(nxt, i + 1, i + j + 2);
lo = Math.min(lo, r[0]);
hi = Math.max(hi, r[1]);
}
} else {
int sp = n + 1 - s, mid = (n - 2 * sp + 1) / 2;
for (int i = 0; i < f; i++) for (int j = 0; j < sp - f; j++) {
int[] r = tourDfs(nxt, i + 1, i + j + mid + 2);
lo = Math.min(lo, r[0]);
hi = Math.max(hi, r[1]);
}
}
tourMemo[n][f][s] = new int[] {lo + 1, hi + 1};
return tourMemo[n][f][s];
}
public static int[] earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
int[] r = tourDfs(n, firstPlayer, secondPlayer);
return new int[] {r[0], r[1]};
}C++
static pair<int, int> tourMemo[29][29][29];
static bool tourSeen[29][29][29];
static pair<int, int> tourDfs(int n, int f, int s) {
if (f + s == n + 1) return {1, 1};
if (f + s > n + 1) { int t = f; f = n + 1 - s; s = n + 1 - t; }
if (tourSeen[n][f][s]) return tourMemo[n][f][s];
int nxt = (n + 1) / 2, lo = 100, hi = 0;
if (s <= nxt) {
for (int i = 0; i < f; i++) for (int j = 0; j < s - f; j++) {
auto r = tourDfs(nxt, i + 1, i + j + 2);
lo = min(lo, r.first);
hi = max(hi, r.second);
}
} else {
int sp = n + 1 - s, mid = (n - 2 * sp + 1) / 2;
for (int i = 0; i < f; i++) for (int j = 0; j < sp - f; j++) {
auto r = tourDfs(nxt, i + 1, i + j + mid + 2);
lo = min(lo, r.first);
hi = max(hi, r.second);
}
}
tourSeen[n][f][s] = true;
tourMemo[n][f][s] = {lo + 1, hi + 1};
return tourMemo[n][f][s];
}
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
auto r = tourDfs(n, firstPlayer, secondPlayer);
return {r.first, r.second};
}JavaScript
var earliestAndLatest = function(n, firstPlayer, secondPlayer) {
var memo = {};
var dfs = function(n, f, s) {
if (f + s === n + 1) return [1, 1];
if (f + s > n + 1) { var t = f; f = n + 1 - s; s = n + 1 - t; }
var key = n * 1024 + f * 32 + s;
if (memo[key]) return memo[key];
var nxt = Math.floor((n + 1) / 2), lo = 100, hi = 0, r, i, j;
if (s <= nxt) {
for (i = 0; i < f; i++) for (j = 0; j < s - f; j++) {
r = dfs(nxt, i + 1, i + j + 2);
if (r[0] < lo) lo = r[0];
if (r[1] > hi) hi = r[1];
}
} else {
var sp = n + 1 - s, mid = Math.floor((n - 2 * sp + 1) / 2);
for (i = 0; i < f; i++) for (j = 0; j < sp - f; j++) {
r = dfs(nxt, i + 1, i + j + mid + 2);
if (r[0] < lo) lo = r[0];
if (r[1] > hi) hi = r[1];
}
}
memo[key] = [lo + 1, hi + 1];
return memo[key];
};
return dfs(n, firstPlayer, secondPlayer);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming