Output Contest Matches - Practice Coding Problems

Output Contest Matches - Problem

During the NBA playoffs, we always set the rather strong team to play with the rather weak team, like making the rank 1 team play with the rank nth team, which is a good strategy to make the contest more interesting.

Given n teams, return their final contest matches in the form of a string. The n teams are labeled from 1 to n, which represents their initial rank (i.e., Rank 1 is the strongest team and Rank n is the weakest team).

We will use parentheses '(', and ')' and commas ',' to represent the contest team pairing. We use the parentheses for pairing and the commas for partition. During the pairing process in each round, you always need to follow the strategy of making the rather strong one pair with the rather weak one.

Input & Output

Example 1 — Basic Case

$ Input: n = 4

› Output: ((1,4),(2,3))

💡 Note: Round 1: Team 1 pairs with team 4, team 2 pairs with team 3, creating matches (1,4) and (2,3). Round 2: The two matches compete against each other, forming ((1,4),(2,3))

Example 2 — Minimum Case

$ Input: n = 2

› Output: (1,2)

💡 Note: With only 2 teams, the strongest (1) pairs directly with the weakest (2), creating the final match (1,2)

Example 3 — Larger Tournament

$ Input: n = 8

› Output: (((1,8),(4,5)),((2,7),(3,6)))

💡 Note: Round 1: (1,8), (2,7), (3,6), (4,5). Round 2: ((1,8),(4,5)), ((2,7),(3,6)). Round 3: Final bracket combines both semifinal matches

Constraints

2 ≤ n ≤ 2¹²
n is a power of 2

Visualization

Tap to expand

Understanding the Visualization

Input Teams

Teams numbered 1 to n (1=strongest, n=weakest)

Pairing Strategy

Strong teams pair with weak teams for fairness

Bracket Output

Nested parentheses represent tournament structure

Key Takeaway

🎯 Key Insight: Pair strongest teams with weakest teams to create fair, exciting tournament brackets

Asked in

G Google 15 M Microsoft 12

The key insight is to pair strongest teams with weakest teams in each round. The recursive approach directly builds the bracket string by dividing the team range and combining results. Best approach is recursive string building with Time: O(n), Space: O(log n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n)	O(n)	Simulate each tournament round by creating arrays of team matchups
Recursive String Building	O(n)	O(log n)	Build the final bracket string directly using recursive divide-and-conquer

Brute Force Simulation — Algorithm Steps

Step 1: Initialize array with team numbers 1 to n
Step 2: For each round, pair first team with last team, second with second-last, etc.
Step 3: Create new array with match strings for next round
Step 4: Repeat until single match remains

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Teams

Start with teams 1, 2, 3, 4

Round 1

Pair strongest with weakest: (1,4), (2,3)

Final

Combine matches: ((1,4),(2,3))

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(int n) {
    char** teams = malloc(n * sizeof(char*));
    for (int i = 0; i < n; i++) {
        teams[i] = malloc(10 * sizeof(char));
        sprintf(teams[i], "%d", i + 1);
    }
    
    int teamCount = n;
    while (teamCount > 1) {
        char** nextRound = malloc((teamCount / 2) * sizeof(char*));
        for (int i = 0; i < teamCount / 2; i++) {
            nextRound[i] = malloc(1000 * sizeof(char));
            sprintf(nextRound[i], "(%s,%s)", teams[i], teams[teamCount - 1 - i]);
        }
        
        for (int i = 0; i < teamCount; i++) {
            free(teams[i]);
        }
        free(teams);
        
        teams = nextRound;
        teamCount /= 2;
    }
    
    char* result = malloc(strlen(teams[0]) + 1);
    strcpy(result, teams[0]);
    
    free(teams[0]);
    free(teams);
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    char* result = solution(n);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each team exactly once across all rounds

✓ Linear Growth

Space Complexity

O(n)

Arrays to store teams and matches in each round

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler