Skip to content

544. Output Contest Matches

Approach 1: Recursive

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  string findContestMatch(int n) {
    vector<string> matches(n);

    for (int i = 0; i < n; ++i)
      matches[i] = to_string(i + 1);

    return generateMatches(matches);
  }

 private:
  string generateMatches(const vector<string>& matches) {
    if (matches.size() == 1)
      return matches[0];

    vector<string> nextMatches;

    for (int i = 0; i < matches.size() / 2; ++i)
      nextMatches.push_back("(" + matches[i] + "," +
                            matches[matches.size() - 1 - i] + ")");

    return generateMatches(nextMatches);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public String findContestMatch(int n) {
    List<String> matches = new ArrayList<>();

    for (int i = 1; i <= n; ++i)
      matches.add(String.valueOf(i));

    return generateMatches(matches);
  }

  private String generateMatches(List<String> matches) {
    if (matches.size() == 1)
      return matches.get(0);

    List<String> nextMatches = new ArrayList<>();

    for (int i = 0; i < matches.size() / 2; ++i)
      nextMatches.add("(" + matches.get(i) + "," + matches.get(matches.size() - 1 - i) + ")");

    return generateMatches(nextMatches);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def findContestMatch(self, n: int) -> str:
    def generateMatches(matches: list[str]) -> str:
      if len(matches) == 1:
        return matches[0]

      nextMatches = []

      for i in range(len(matches) // 2):
        nextMatches.append(
            '(' + matches[i] + ',' + matches[len(matches) - 1 - i] + ')')

      return generateMatches(nextMatches)

    return generateMatches([str(i + 1) for i in range(n)])

Approach 2: Iterative

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  string findContestMatch(int n) {
    vector<string> matches(n);

    for (int i = 0; i < n; ++i)
      matches[i] = to_string(i + 1);

    while (n > 1) {
      for (int i = 0; i < n / 2; ++i)
        matches[i] = "(" + matches[i] + "," + matches[n - 1 - i] + ")";
      n /= 2;
    }

    return matches[0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public String findContestMatch(int n) {
    String[] matches = new String[n];

    for (int i = 0; i < n; ++i)
      matches[i] = String.valueOf(i + 1);

    while (n > 1) {
      for (int i = 0; i < n / 2; ++i)
        matches[i] = "(" + matches[i] + "," + matches[n - 1 - i] + ")";
      n /= 2;
    }

    return matches[0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def findContestMatch(self, n: int) -> str:
    matches = [str(i + 1) for i in range(n)]

    while n > 1:
      for i in range(n // 2):
        matches[i] = '(' + matches[i] + ',' + matches[n - 1 - i] + ')'
      n //= 2

    return matches[0]