Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Output Contest Matches in Java: Pair the Ends, Recurse by Round

Construct ranked tournament brackets round by round, understand Java reference passing, and count the real String-copying cost.

MediumRecursion and backtrackingPattern: recursion, two pointers

Problem statement

Teams have ranks 1 through n. Pair the strongest remaining entry with the weakest, the second strongest with the second weakest, and continue each round until one bracket expression remains. Return that expression using parentheses and commas.

We construct a schedule, not scores or actual winners. The supplied task uses n=2^x for 1≤x≤12, ensuring no byes are needed. LeetCode Output Contest Matches may require Premium and uses its own bounds. The method rejects n<2 and non-powers of two instead of silently discarding an unpaired team.

Constraints & requirements

CONTRACT
Original task: n=2^x with 1≤x≤12. LeetCode access/bounds may differ. Every new round halves the list; preserve its rank order. LeetCode may require Premium.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    n=4
    Output
    "((1,4),(2,3))"

    First build (1,4) and (2,3), then pair those expressions.

  2. Example 2 Case 2

    Input
    n=2
    Output
    "(1,2)"

    One round creates the whole bracket.

  3. Example 3 Case 3

    Input
    n=8
    Output
    "(((1,8),(4,5)),((2,7),(3,6)))"

    Next-round pairing uses opposite ends again, not adjacent entries.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Treat a whole prior match as one entry for the next round.

02Hint 2

Use left and right pointers to pair strongest with weakest.

03Hint 3

Return the recursive result because assigning a new list does not reassign the caller’s reference.

How to think before coding

Treat an entire match string as one ranked entry in the next round. Pair index left with index right, then move both inward. A new round halves the list; a one-entry list is complete. Return the child’s final expression. Pairing adjacent entries after the first round would change the prescribed strongest-versus-weakest rule.

Brute force and the improvement

Start with a list of team labels. In each round, loop from the two ends, pair the strongest with the weakest, and replace the list with those match strings. This direct round simulation is already the right baseline: the problem fixes the bracket rather than asking us to search all possible tournaments. The recursive code below performs the SAME rounds and has the same string-building costs; recursion is a teaching representation, not an asymptotic improvement. The complexity section accounts for copied labels and intermediate strings.

Intuition: a match becomes one next-round entry

For [1,2,3,4], the first round becomes [(1,4),(2,3)]. Those expressions can be treated like team labels for the next round. Pair them to get ((1,4),(2,3)).

For eight teams, do not pair adjacent first-round matches automatically. Pair opposite ends again: (1,8) meets (4,5), and (2,7) meets (3,6).

Every round halves the list. Recursion can therefore solve the same problem on that smaller next-round list.

Algorithm

  1. Build ascending string labels 1 through n.
  2. If one expression remains, return it.
  3. Pair left and right entries as (left,right).
  4. Move both pointers inward, collecting the next-round expressions.
  5. Return the recursive result for the new list.

Java solution

Each call builds the next round and returns the final expression. The wrapper checks that the number of teams is a supported power of two.

Java
import java.util.*;

class Solution {
    public static String findContestMatch(int n) {
        if (n < 2 || (n & (n - 1)) != 0) throw new IllegalArgumentException("n must be a power of 2 >= 2");
        List<String> teams = new ArrayList<>();
        for (int i = 1; i <= n; i++) teams.add(String.valueOf(i)); // Initial ranking is ascending.
        return pairRound(teams); // Return the final bracket; do not reassign a caller's list reference.
    }
    private static String pairRound(List<String> teams) {
        if (teams.size() == 1) return teams.get(0); // This expression represents the whole tournament.
        List<String> next = new ArrayList<>();
        for (int left = 0, right = teams.size() - 1; left < right; left++, right--) {
            next.add("(" + teams.get(left) + "," + teams.get(right) + ")"); // Strongest remaining vs weakest.
        }
        return pairRound(next); // Each round halves the number of bracket entries.
    }

    public static void main(String[] args) {
        System.out.println(findContestMatch(4)); // ((1,4),(2,3))
    }
}

The invocation returns ((1,4),(2,3)). Java passes a copy of a reference: teams = next changes only a local reference, while teams.clear() mutates the shared list. Returning the recursive result avoids relying on either effect.

Round chain and dry run

Numbered illustrated dry run for Output Contest Matches; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: n = 4

What to track: teams contains expressions for the current round. left and right pair the strongest remaining entry with the weakest; next is a fresh list.

  1. Create the initial ranking

    Java operationfor (int i = 1; i <= n; i++) teams.add(String.valueOf(i));
    Stateteams = ["1","2","3","4"]

    The power-of-two check has passed. There are four entries in the first round.

  2. Pair opposite ends

    Java operationnext.add("(" + teams.get(left) + "," + teams.get(right) + ")");
    Stateleft = 0; right = 3; next = ["(1,4)"]

    Ranking 1 is paired with ranking 4, not the adjacent entry 2.

  3. Move both pointers inward

    Java operationnext.add("(" + teams.get(left) + "," + teams.get(right) + ")");
    Stateleft = 1; right = 2; next = ["(1,4)","(2,3)"]

    left < right becomes false after this pair, completing the first round.

  4. Recurse on the smaller round

    Java operationreturn pairRound(next);
    Statenew teams = ["(1,4)","(2,3)"]; its next list becomes ["((1,4),(2,3))"]

    The call halves the number of entries while preserving the order of the bracket expressions.

  5. Return the only remaining expression

    Java operationif (teams.size() == 1) return teams.get(0);
    Stateteams.size() = 1; return "((1,4),(2,3))" through both waiting calls

    No further pairing is needed. Returning a String avoids relying on a reassigned list reference to update the caller.

Final result: "((1,4),(2,3))"

Worked example · read from top to bottom
pairRound([1,2,3,4,5,6,7,8])
  → pairRound([(1,8),(2,7),(3,6),(4,5)])
    → pairRound([((1,8),(4,5)),((2,7),(3,6))])
      → pairRound([(((1,8),(4,5)),((2,7),(3,6)))])
        → return the only expression

There is one recursive child per round. Multiple matches are created by a loop inside that call, not by independently branching recursive searches.

Why it works

Each round pairs every entry exactly once, from strongest-ranked end to weakest-ranked end. The list of resulting expressions preserves the ordering needed by the next round. The base expression contains every original team once and the required nesting for all rounds. The power-of-two assumption ensures every intermediate list can be paired completely.

Complexity and alternative approaches

There are O(n) pairing operations in the geometric sequence n/2+n/4+…+1. However, Java Strings are immutable and copying a growing expression is not O(1).

Let S be the final bracket’s character length, including numeric team labels. Across O(log n) rounds, concatenation copies O(S) characters per round in a worst-case bound: O(S log n) time. S is O(n log n) when decimal team-label lengths are counted, making O(n log²n) a general upper bound. Treating labels as fixed-width tokens simplifies this to O(n log n) character-copying work, not O(n).

Because recursive callers retain their lists, live intermediate strings can use O(S log n) space, plus O(log n) frames. An iterative round loop lets obsolete lists become collectible and uses O(S) peak live storage. A tree of pairing nodes built in O(n) structural work, followed by one StringBuilder traversal, avoids repeatedly copying whole subtree strings.

Common mistakes

  • Pairing adjacent entries instead of opposite ends.
  • Returning the first-round list rather than the final nested expression.
  • Reassigning a list parameter and expecting the caller’s reference to change.
  • Reporting O(n) Java time while treating long concatenations as constant work.
  • Accepting an odd team count without defining byes.

Practice next

Next lessonPow(x,n)

Back to Recursion and backtracking →