Find Champion I

Easy

Asked by:

18 views

Topics:

Arrays

There are n teams numbered from 0 to n - 1 in a tournament.

Given a 0-indexed 2D boolean matrix grid of size n * n. For all i, j that 0 <= i, j <= n - 1 and i != j team i is stronger than team j if grid[i][j] == 1, otherwise, team j is stronger than team i.

Team a will be the champion of the tournament if there is no team b that is stronger than team a.

Return the team that will be the champion of the tournament.

Example 1:

Input: grid = [[0,1],[0,0]]
Output: 0
Explanation: There are two teams in this tournament.
grid[0][1] == 1 means that team 0 is stronger than team 1. So team 0 will be the champion.

Example 2:

Input: grid = [[0,0,1],[1,0,1],[0,0,0]]
Output: 1
Explanation: There are three teams in this tournament.
grid[1][0] == 1 means that team 1 is stronger than team 0.
grid[1][2] == 1 means that team 1 is stronger than team 2.
So team 1 will be the champion.

Constraints:

n == grid.length
n == grid[i].length
2 <= n <= 100
grid[i][j] is either 0 or 1.
For all i grid[i][i] is 0.
For all i, j that i != j, grid[i][j] != grid[j][i].
The input is generated such that if team a is stronger than team b and team b is stronger than team c, then team a is stronger than team c.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected data type of the input adjacency matrix? Can I assume it will always be a square matrix representing a valid tournament?
What should the function return if there is no champion (e.g., if the input is an empty matrix or if there is a cycle in the tournament)?
What are the constraints on the size of the matrix? Is there a practical upper bound on the number of nodes in the tournament?
Is it possible for there to be multiple nodes that could be considered 'champions' according to the provided definition? If so, is there a specific champion I should return, or can I return any one of them?
Does the matrix always represent a valid tournament, meaning that for any two nodes i and j, either matrix[i][j] or matrix[j][i] is 1, but not both?

Brute Force Solution

Approach

We want to find the champion by checking every player against every other player. The brute force way is to compare each player to all the others to see if they win every time.

Here's how the algorithm would work step-by-step:

Pick a player.
Compare that player to every other player in the group.
If the chosen player loses against any other player, they are not the champion, so move on to the next player.
If the chosen player wins against every single other player, then this player is the champion.

Code Implementation

def find_champion_brute_force(tournament_results):
    number_of_players = len(tournament_results)

    for potential_champion in range(number_of_players):

        is_champion = True

        # Compare current player with every other player

        for opponent in range(number_of_players):
            # A player can't be a champion if they lose to anyone

            if tournament_results[potential_champion][opponent] == 0 and potential_champion != opponent:

                is_champion = False

                break

        # If the player beats everyone, they are the champion.
        if is_champion:

            return potential_champion

    return -1

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n players to potentially find a champion. For each player, it then compares them against every other player, which involves another n-1 comparisons. Therefore, in the worst case, we are performing approximately n * (n-1) comparisons. This can be approximated as n * n/2, resulting in a time complexity of O(n²).

Space Complexity

O(1) – The algorithm iterates through players and compares each to the others. The operations described involve only comparing elements in place and don't imply the creation of any auxiliary data structures like arrays, hashmaps or significant recursion. Only a few variables, such as loop counters or a champion indicator, might be used which take up constant space, irrespective of the number of players. Therefore, the space complexity is constant and independent of the input size N, where N is the number of players.

Optimal Solution

Approach

To find the champion, we are looking for the single team that beats all other teams. The efficient approach is to realize that if a team loses to anyone, it cannot be the champion. We use this knowledge to quickly eliminate losing teams, leaving us with the potential champion.

Here's how the algorithm would work step-by-step:

Assume that the first team is the potential champion.
Go through each of the other teams one by one.
For each other team, check if the potential champion loses to them.
If the potential champion loses, that other team becomes the new potential champion.
Keep going until we have checked all the other teams.
The team that remains as the potential champion at the end is the real champion.

Code Implementation

def find_champion(grid):
    potential_champion = 0

    # Iterate through all other teams
    for other_team in range(1, len(grid)):

        # If potential champion loses, update it
        if grid[potential_champion][other_team] == 0:
            potential_champion = other_team

            # This team is the new potential champion

    # The loop finishes; this is our champion
    return potential_champion

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n teams in the input array once, comparing the current potential champion against each other team. Inside the loop, it performs a single comparison to see if the current potential champion loses to the other team. This single loop execution results in a time complexity that is directly proportional to the number of teams.

Space Complexity

O(1) – The algorithm only uses a single variable to store the index of the potential champion. No additional data structures are used, and the size of this variable remains constant regardless of the number of teams. Therefore, the auxiliary space complexity is constant, or O(1).

Edge Cases

Case	How to Handle
Input array is null	Throw an IllegalArgumentException or return a predefined error value like -1.
Input array is empty	Return -1, indicating no champion can be found.
The input is a square matrix with dimensions 1x1	Return 0 as the single node is a champion.
Matrix is not square (rows != cols)	Throw an IllegalArgumentException, as the problem expects a square adjacency matrix.
Matrix represents a disconnected graph	The current algorithm will still find a champion if it exists, defined as a node that wins against all others.
The matrix contains invalid values (not 0 or 1)	Throw IllegalArgumentException since the matrix should only contain 0 and 1.
There are multiple champions (violates problem constraint)	The problem states there is only one champion so the function should return the first one it finds.
Large matrix exceeding memory limits	Consider using more memory-efficient data structures if possible, or employing a divide-and-conquer approach if feasible to reduce memory footprint.

Input array is null

How to Handle:

Throw an IllegalArgumentException or return a predefined error value like -1.

Input array is empty

How to Handle:

Return -1, indicating no champion can be found.

The input is a square matrix with dimensions 1x1

How to Handle:

Return 0 as the single node is a champion.

Matrix is not square (rows != cols)

How to Handle:

Throw an IllegalArgumentException, as the problem expects a square adjacency matrix.

Matrix represents a disconnected graph

How to Handle:

The current algorithm will still find a champion if it exists, defined as a node that wins against all others.

The matrix contains invalid values (not 0 or 1)

How to Handle:

Throw IllegalArgumentException since the matrix should only contain 0 and 1.

There are multiple champions (violates problem constraint)

How to Handle:

The problem states there is only one champion so the function should return the first one it finds.

Large matrix exceeding memory limits

How to Handle:

Consider using more memory-efficient data structures if possible, or employing a divide-and-conquer approach if feasible to reduce memory footprint.