Problem

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, theearliest possible round number and the latest possible round number in which these two players will compete against each other, respectively.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

1
2
3
4

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

Solution

Method 1 - Backtracking (Full Simulation)

Simulate all possible match outcomes for non-best players using backtracking. This ensures all scenarios are explored, but may be slow for larger n.

Method 2 - State-Memoized DFS (Optimized)

We optimize by memoizing the state of the recursive function using a key. The key is constructed by concatenating the number of remaining players before the first player, the number between the first and second player, and the number after the second player, separated by ‘|’. Each count represents a player still in the tournament (value = 1). This key is stored in a visited set to prevent redundant computations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <vector>
#include <string>
#include <unordered_set>
#include <climits>
using namespace std;

class Solution {
public:
    int f, s, n;
    int maxr = INT_MIN, minr = INT_MAX;
    unordered_set<string> visited;

    vector<int> earliestAndLatest(int N, int F, int S) {
        f = F-1, s = S-1, n = N;
        string players(n, '1');
        help(players, 0, n-1, 1);
        return {minr, maxr};
    }

    void help(string &players, int l, int r, int round) {
        if (l >= r) {
            help(players, 0, n-1, round+1);
            return;
        }
        if (players[l] == '0') {
            help(players, l+1, r, round);
            return;
        }
        if (players[r] == '0') {
            help(players, l, r-1, round);
            return;
        }
        if ((l == f && r == s) || (l == s && r == f)) {
            minr = min(minr, round);
            maxr = max(maxr, round);
            return;
        }
        if (l == f || l == s) {
            char tmp = players[r];
            players[r] = '0';
            help(players, l+1, r-1, round);
            players[r] = tmp;
            return;
        }
        if (r == f || r == s) {
            char tmp = players[l];
            players[l] = '0';
            help(players, l+1, r-1, round);
            players[l] = tmp;
            return;
        }
        string key = getKey(players);
        if (visited.count(key)) return;
        visited.insert(key);
        // Try both outcomes
        char tmp = players[r];
        players[r] = '0';
        help(players, l+1, r-1, round);
        players[r] = tmp;
        tmp = players[l];
        players[l] = '0';
        help(players, l+1, r-1, round);
        players[l] = tmp;
    }

    string getKey(const string &s1) {
        int d1 = 0, d2 = 0, d3 = 0;
        for (int i = 0; i < s1.size(); ++i) {
            if (i < min(f, s) && s1[i] == '1') d1++;
            else if (i > min(f, s) && i < max(f, s) && s1[i] == '1') d2++;
            else if (i > max(f, s) && s1[i] == '1') d3++;
        }
        return to_string(d1) + "|" + to_string(d2) + "|" + to_string(d3);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

import java.util.*;
class Solution {
    int f, s, n;
    int minr = Integer.MAX_VALUE, maxr = Integer.MIN_VALUE;
    Set<String> visited = new HashSet<>();

    public int[] earliestAndLatest(int N, int F, int S) {
        f = F-1; s = S-1; n = N;
        char[] players = new char[n];
        Arrays.fill(players, '1');
        help(players, 0, n-1, 1);
        return new int[]{minr, maxr};
    }

    void help(char[] players, int l, int r, int round) {
        if (l >= r) {
            help(players, 0, n-1, round+1);
            return;
        }
        if (players[l] == '0') {
            help(players, l+1, r, round);
            return;
        }
        if (players[r] == '0') {
            help(players, l, r-1, round);
            return;
        }
        if ((l == f && r == s) || (l == s && r == f)) {
            minr = Math.min(minr, round);
            maxr = Math.max(maxr, round);
            return;
        }
        if (l == f || l == s) {
            char tmp = players[r];
            players[r] = '0';
            help(players, l+1, r-1, round);
            players[r] = tmp;
            return;
        }
        if (r == f || r == s) {
            char tmp = players[l];
            players[l] = '0';
            help(players, l+1, r-1, round);
            players[l] = tmp;
            return;
        }
        String key = getKey(players);
        if (visited.contains(key)) return;
        visited.add(key);
        char tmp = players[r];
        players[r] = '0';
        help(players, l+1, r-1, round);
        players[r] = tmp;
        tmp = players[l];
        players[l] = '0';
        help(players, l+1, r-1, round);
        players[l] = tmp;
    }

    String getKey(char[] s1) {
        int d1 = 0, d2 = 0, d3 = 0;
        for (int i = 0; i < s1.length; i++) {
            if (i < Math.min(f, s) && s1[i] == '1') d1++;
            else if (i > Math.min(f, s) && i < Math.max(f, s) && s1[i] == '1') d2++;
            else if (i > Math.max(f, s) && s1[i] == '1') d3++;
        }
        return d1 + "|" + d2 + "|" + d3;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

def earliestAndLatest(n: int, firstPlayer: int, secondPlayer: int) -> [int, int]:
    minr, maxr = float('inf'), float('-inf')
    visited = set()
    f, s = firstPlayer-1, secondPlayer-1

    def get_key(players):
        d1 = d2 = d3 = 0
        for i, v in enumerate(players):
            if i < min(f, s) and v == '1': d1 += 1
            elif min(f, s) < i < max(f, s) and v == '1': d2 += 1
            elif i > max(f, s) and v == '1': d3 += 1
        return f"{d1}|{d2}|{d3}"

    def help(players, l, r, round):
        nonlocal minr, maxr
        if l >= r:
            help(players, 0, n-1, round+1)
            return
        if players[l] == '0':
            help(players, l+1, r, round)
            return
        if players[r] == '0':
            help(players, l, r-1, round)
            return
        if (l == f and r == s) or (l == s and r == f):
            minr = min(minr, round)
            maxr = max(maxr, round)
            return
        if l == f or l == s:
            players2 = players[:r] + '0' + players[r+1:]
            help(players2, l+1, r-1, round)
            return
        if r == f or r == s:
            players2 = players[:l] + '0' + players[l+1:]
            help(players2, l+1, r-1, round)
            return
        key = get_key(players)
        if key in visited:
            return
        visited.add(key)
        # Both can win
        players2 = players[:r] + '0' + players[r+1:]
        help(players2, l+1, r-1, round)
        players2 = players[:l] + '0' + players[l+1:]
        help(players2, l+1, r-1, round)

    players = '1' * n
    help(players, 0, n-1, 1)
    return [int(minr), int(maxr)]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

use std::collections::HashSet;
pub fn earliest_and_latest(n: i32, first_player: i32, second_player: i32) -> Vec<i32> {
    fn get_key(players: &Vec<u8>, f: usize, s: usize) -> String {
        let mut d1 = 0; let mut d2 = 0; let mut d3 = 0;
        for (i, &v) in players.iter().enumerate() {
            if i < f.min(s) && v == b'1' { d1 += 1; }
            else if i > f.min(s) && i < f.max(s) && v == b'1' { d2 += 1; }
            else if i > f.max(s) && v == b'1' { d3 += 1; }
        }
        format!("{}|{}|{}", d1, d2, d3)
    }
    fn help(players: &mut Vec<u8>, l: usize, r: usize, round: i32, n: usize, f: usize, s: usize, minr: &mut i32, maxr: &mut i32, visited: &mut HashSet<String>) {
        if l >= r {
            help(players, 0, n-1, round+1, n, f, s, minr, maxr, visited);
            return;
        }
        if players[l] == b'0' {
            help(players, l+1, r, round, n, f, s, minr, maxr, visited);
            return;
        }
        if players[r] == b'0' {
            help(players, l, r-1, round, n, f, s, minr, maxr, visited);
            return;
        }
        if (l == f && r == s) || (l == s && r == f) {
            *minr = (*minr).min(round);
            *maxr = (*maxr).max(round);
            return;
        }
        if l == f || l == s {
            let tmp = players[r];
            players[r] = b'0';
            help(players, l+1, r-1, round, n, f, s, minr, maxr, visited);
            players[r] = tmp;
            return;
        }
        if r == f || r == s {
            let tmp = players[l];
            players[l] = b'0';
            help(players, l+1, r-1, round, n, f, s, minr, maxr, visited);
            players[l] = tmp;
            return;
        }
        let key = get_key(players, f, s);
        if visited.contains(&key) { return; }
        visited.insert(key);
        let tmp = players[r];
        players[r] = b'0';
        help(players, l+1, r-1, round, n, f, s, minr, maxr, visited);
        players[r] = tmp;
        let tmp = players[l];
        players[l] = b'0';
        help(players, l+1, r-1, round, n, f, s, minr, maxr, visited);
        players[l] = tmp;
    }
    let mut minr = i32::MAX;
    let mut maxr = i32::MIN;
    let mut players = vec![b'1'; n as usize];
    let mut visited = HashSet::new();
    let f = (first_player - 1) as usize;
    let s = (second_player - 1) as usize;
    help(&mut players, 0, n as usize - 1, 1, n as usize, f, s, &mut minr, &mut maxr, &mut visited);
    vec![minr, maxr]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

function earliestAndLatest(n: number, firstPlayer: number, secondPlayer: number): number[] {
    let minr = Infinity, maxr = -Infinity;
    const visited = new Set<string>();
    const f = firstPlayer - 1, s = secondPlayer - 1;

    function getKey(players: string): string {
        let d1 = 0, d2 = 0, d3 = 0;
        for (let i = 0; i < players.length; ++i) {
            if (i < Math.min(f, s) && players[i] === '1') d1++;
            else if (i > Math.min(f, s) && i < Math.max(f, s) && players[i] === '1') d2++;
            else if (i > Math.max(f, s) && players[i] === '1') d3++;
        }
        return `${d1}|${d2}|${d3}`;
    }

    function help(players: string, l: number, r: number, round: number) {
        if (l >= r) {
            help(players, 0, n-1, round+1);
            return;
        }
        if (players[l] === '0') {
            help(players, l+1, r, round);
            return;
        }
        if (players[r] === '0') {
            help(players, l, r-1, round);
            return;
        }
        if ((l === f && r === s) || (l === s && r === f)) {
            minr = Math.min(minr, round);
            maxr = Math.max(maxr, round);
            return;
        }
        if (l === f || l === s) {
            help(players.substring(0, r) + '0' + players.substring(r+1), l+1, r-1, round);
            return;
        }
        if (r === f || r === s) {
            help(players.substring(0, l) + '0' + players.substring(l+1), l+1, r-1, round);
            return;
        }
        const key = getKey(players);
        if (visited.has(key)) return;
        visited.add(key);
        help(players.substring(0, r) + '0' + players.substring(r+1), l+1, r-1, round);
        help(players.substring(0, l) + '0' + players.substring(l+1), l+1, r-1, round);
    }

    help('1'.repeat(n), 0, n-1, 1);
    return [minr, maxr];
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <vector>
#include <algorithm>
using namespace std;

void dfs(vector<int>& players, int round, int a, int b, int& minr, int& maxr) {
    int n = players.size();
    int i = 0, j = n - 1;
    while (i < j) {
        if ((players[i] == a && players[j] == b) || (players[i] == b && players[j] == a)) {
            minr = min(minr, round);
            maxr = max(maxr, round);
            return;
        }
        ++i; --j;
    }
    vector<pair<int, int>> matches;
    i = 0; j = n - 1;
    while (i < j) {
        matches.push_back({players[i], players[j]});
        ++i; --j;
    }
    vector<int> next;
    if (n % 2 == 1) next.push_back(players[n/2]);
    int m = matches.size();
    int total = 1 << m;
    for (int mask = 0; mask < total; ++mask) {
        vector<int> cur = next;
        for (int k = 0; k < m; ++k) {
            int x = matches[k].first, y = matches[k].second;
            if ((x == a || x == b) && (y == a || y == b)) continue;
            if (x == a || x == b) cur.push_back(x);
            else if (y == a || y == b) cur.push_back(y);
            else cur.push_back((mask & (1 << k)) ? x : y);
        }
        sort(cur.begin(), cur.end());
        dfs(cur, round + 1, a, b, minr, maxr);
    }
}

vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
    vector<int> players(n);
    for (int i = 0; i < n; ++i) players[i] = i + 1;
    int minr = 100, maxr = 0;
    dfs(players, 1, firstPlayer, secondPlayer, minr, maxr);
    return {minr, maxr};
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
    int minr = 100, maxr = 0;
    public int[] earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
        List<Integer> players = new ArrayList<>();
        for (int i = 1; i <= n; ++i) players.add(i);
        dfs(players, 1, firstPlayer, secondPlayer);
        return new int[]{minr, maxr};
    }
    private void dfs(List<Integer> players, int round, int a, int b) {
        int n = players.size();
        int i = 0, j = n - 1;
        while (i < j) {
            int x = players.get(i), y = players.get(j);
            if ((x == a && y == b) || (x == b && y == a)) {
                minr = Math.min(minr, round);
                maxr = Math.max(maxr, round);
                return;
            }
            ++i; --j;
        }
        List<int[]> matches = new ArrayList<>();
        i = 0; j = n - 1;
        while (i < j) {
            matches.add(new int[]{players.get(i), players.get(j)});
            ++i; --j;
        }
        List<Integer> next = new ArrayList<>();
        if (n % 2 == 1) next.add(players.get(n/2));
        int m = matches.size();
        int total = 1 << m;
        for (int mask = 0; mask < total; ++mask) {
            List<Integer> cur = new ArrayList<>(next);
            for (int k = 0; k < m; ++k) {
                int x = matches.get(k)[0], y = matches.get(k)[1];
                if ((x == a || x == b) && (y == a || y == b)) continue;
                if (x == a || x == b) cur.add(x);
                else if (y == a || y == b) cur.add(y);
                else cur.add(((mask & (1 << k)) != 0) ? x : y);
            }
            Collections.sort(cur);
            dfs(cur, round + 1, a, b);
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

def earliestAndLatest(n: int, firstPlayer: int, secondPlayer: int) -> [int, int]:
    minr, maxr = 100, 0
    def dfs(players, round):
        nonlocal minr, maxr
        i, j = 0, len(players) - 1
        while i < j:
            if (players[i] == firstPlayer and players[j] == secondPlayer) or (players[i] == secondPlayer and players[j] == firstPlayer):
                minr = min(minr, round)
                maxr = max(maxr, round)
                return
            i += 1; j -= 1
        matches = []
        i, j = 0, len(players) - 1
        while i < j:
            matches.append((players[i], players[j]))
            i += 1; j -= 1
        nexts = []
        if len(players) % 2 == 1:
            nexts.append([players[len(players)//2]])
        else:
            nexts = [[]]
        m = len(matches)
        for mask in range(1 << m):
            for base in nexts:
                cur = base[:]
                for k in range(m):
                    x, y = matches[k]
                    if (x == firstPlayer or x == secondPlayer) and (y == firstPlayer or y == secondPlayer):
                        continue
                    if x == firstPlayer or x == secondPlayer:
                        cur.append(x)
                    elif y == firstPlayer or y == secondPlayer:
                        cur.append(y)
                    else:
                        cur.append(x if (mask & (1 << k)) else y)
                cur.sort()
                dfs(cur, round + 1)
    dfs(list(range(1, n+1)), 1)
    return [minr, maxr]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

pub fn earliest_and_latest(n: i32, first_player: i32, second_player: i32) -> Vec<i32> {
    fn dfs(players: Vec<i32>, round: i32, a: i32, b: i32, minr: &mut i32, maxr: &mut i32) {
        let n = players.len();
        let mut i = 0;
        let mut j = n - 1;
        while i < j {
            if (players[i] == a && players[j] == b) || (players[i] == b && players[j] == a) {
                *minr = (*minr).min(round);
                *maxr = (*maxr).max(round);
                return;
            }
            i += 1;
            j -= 1;
        }
        let mut matches = vec![];
        let mut i = 0;
        let mut j = n - 1;
        while i < j {
            matches.push((players[i], players[j]));
            i += 1;
            j -= 1;
        }
        let mut nexts = vec![];
        if n % 2 == 1 {
            nexts.push(vec![players[n/2]]);
        } else {
            nexts.push(vec![]);
        }
        let m = matches.len();
        for mask in 0..(1 << m) {
            for base in &nexts {
                let mut cur = base.clone();
                for k in 0..m {
                    let (x, y) = matches[k];
                    if (x == a || x == b) && (y == a || y == b) {
                        continue;
                    }
                    if x == a || x == b {
                        cur.push(x);
                    } else if y == a || y == b {
                        cur.push(y);
                    } else {
                        cur.push(if (mask & (1 << k)) != 0 { x } else { y });
                    }
                }
                let mut cur_sorted = cur.clone();
                cur_sorted.sort();
                dfs(cur_sorted, round + 1, a, b, minr, maxr);
            }
        }
    }
    let mut players = (1..=n).collect::<Vec<_>>();
    let mut minr = 100;
    let mut maxr = 0;
    dfs(players, 1, first_player, second_player, &mut minr, &mut maxr);
    vec![minr, maxr]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

function earliestAndLatest(n: number, firstPlayer: number, secondPlayer: number): number[] {
    let minr = 100, maxr = 0;
    function dfs(players: number[], round: number) {
        let i = 0, j = players.length - 1;
        while (i < j) {
            if ((players[i] === firstPlayer && players[j] === secondPlayer) || (players[i] === secondPlayer && players[j] === firstPlayer)) {
                minr = Math.min(minr, round);
                maxr = Math.max(maxr, round);
                return;
            }
            ++i; --j;
        }
        let matches: [number, number][] = [];
        i = 0; j = players.length - 1;
        while (i < j) {
            matches.push([players[i], players[j]]);
            ++i; --j;
        }
        let nexts: number[][] = players.length % 2 === 1 ? [[players[Math.floor(players.length/2)]]] : [[]];
        let m = matches.length;
        for (let mask = 0; mask < (1 << m); ++mask) {
            for (const base of nexts) {
                let cur = base.slice();
                for (let k = 0; k < m; ++k) {
                    let [x, y] = matches[k];
                    if ((x === firstPlayer || x === secondPlayer) && (y === firstPlayer || y === secondPlayer)) continue;
                    if (x === firstPlayer || x === secondPlayer) cur.push(x);
                    else if (y === firstPlayer || y === secondPlayer) cur.push(y);
                    else cur.push((mask & (1 << k)) ? x : y);
                }
                cur.sort((a, b) => a - b);
                dfs(cur, round + 1);
            }
        }
    }
    dfs(Array.from({length: n}, (_, i) => i + 1), 1);
    return [minr, maxr];
}

Complexity

  • ⏰ Time complexity: O(n^3) (with memoization, n ≤ 28).
  • 🧺 Space complexity: O(n^3) for the memoization table.