234. Tennis Match Tournament Results

Tennis Match Tournament Results

You are given a list of tennis player ranks. A smaller rank means a better player. In every round, players are matched in consecutive pairs from left to right. From each pair, the better ranked player advances to the next round. Repeat this process until only one player remains.

Return the winner of the tournament and record the winners after each elimination round. All ranks are distinct.

You also need to find an ordering of the same ranks such that better ranked players are eliminated as late as possible. In an optimal ordering, after every round, the best possible remaining ranks should survive. If multiple optimal orderings exist, return the lexicographically smallest one.

Class

Tennis Match Tournament

TennisMatchTournament()

Creates an object that can evaluate tennis match tournament results.

Methods

Tournament Winner

int tournamentWinner(List<Integer> ranks)

Returns the rank of the final winner.
In every match, the smaller rank wins.
Players are matched in consecutive pairs starting from index 0.
If a round has an odd number of players, the last unmatched player advances automatically.

Elimination Rounds

List<String> eliminationRounds(List<Integer> ranks)

Returns the result after each elimination round.
Each string contains the advancing ranks of that round, separated by commas.
The final string contains only the tournament winner.
If the input has one rank, return a list containing that rank as one string.

Optimal Ordering

List<Integer> optimalOrdering(List<Integer> ranks)

Returns an ordering of the given ranks such that better ranked players are eliminated as late as possible.
After each round, if m players advance, those m players must be the smallest m ranks among the original input.
The advancing ranks must remain in their actual left-to-right order after that round, not sorted.
This continues until only the best rank remains.
If the number of players is not a power of 2, unmatched players advance automatically using the same left-to-right pairing rule.
If more than one optimal ordering exists, return the lexicographically smallest ordering.

Constraints

1 ≤ ranks.size() ≤ 100,000
1 ≤ ranks[i] ≤ 1,000,000,000
All values in ranks are distinct.
The better ranked player is the player with the smaller rank value.
The input list must not be empty.
No parameter value will be null.

Examples

Example 1

tournamentWinner(ranks = [9, 4, 7, 2, 6, 1, 8, 3])

Round 1 winners are [4, 2, 1, 3].
Round 2 winners are [2, 1].
Round 3 winner is [1].
Output: 1

Example 2

eliminationRounds(ranks = [9, 4, 7, 2, 6, 1, 8, 3])

Round 1 winners are [4, 2, 1, 3].
Round 2 winners are [2, 1].
Round 3 winner is [1].
Output: ["4,2,1,3", "2,1", "1"]

Example 3

optimalOrdering(ranks = [1, 2, 3, 4])

The lexicographically smallest optimal ordering is [1, 3, 2, 4].
After round 1, ranks [1, 2] survive.
After round 2, rank [1] wins.
Output: [1, 3, 2, 4]

Example 4

optimalOrdering(ranks = [5, 1, 4, 2, 3])

The lexicographically smallest optimal ordering is [1, 4, 3, 5, 2].
After round 1, ranks [1, 3, 2] survive.
After round 2, ranks [1, 2] survive.
After round 3, rank [1] wins.
Output: [1, 4, 3, 5, 2]

Example 5

eliminationRounds(ranks = [7])

There is only one player, so no match is played.
Output: ["7"]