Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

544. Output Contest Matches

Time: $O(n)$

Space: $O(n)$

			


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);
  }
};




			


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);
  }
}




			


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)])