Find Champion II

Medium

Asked by:

31 views

Topics:

Graphs

There are n teams numbered from 0 to n - 1 in a tournament; each team is also a node in a DAG.

You are given the integer n and a 0-indexed 2D integer array edges of length m representing the DAG, where edges[i] = [u_i, v_i] indicates that there is a directed edge from team u_i to team v_i in the graph.

A directed edge from a to b in the graph means that team a is stronger than team b and team b is weaker than team a.

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 if there is a unique champion, otherwise, return -1.

Notes

A cycle is a series of nodes a₁, a₂, ..., a_n, a_n+1 such that node a₁ is the same node as node a_n+1, the nodes a₁, a₂, ..., a_n are distinct, and there is a directed edge from the node a_i to node a_i+1 for every i in the range [1, n].
A DAG is a directed graph that does not have any cycle.

Example 1:

Input: n = 3, edges = [[0,1],[1,2]]
Output: 0
Explanation: Team 1 is weaker than team 0. Team 2 is weaker than team 1. So the champion is team 0.

Example 2:

Input: n = 4, edges = [[0,2],[1,3],[1,2]]
Output: -1
Explanation: Team 2 is weaker than team 0 and team 1. Team 3 is weaker than team 1. But team 1 and team 0 are not weaker than any other teams. So the answer is -1.

Constraints:

1 <= n <= 100
m == edges.length
0 <= m <= n * (n - 1) / 2
edges[i].length == 2
0 <= edge[i][j] <= n - 1
edges[i][0] != edges[i][1]
The input is generated such that if team a is stronger than team b, team b is not stronger than team a.
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:

If there are multiple potential champions (nodes with no incoming edges), should I return any one of them, or is there a specific criterion for choosing between them?
What is the range of values for 'n', the number of teams? Can 'n' be zero or negative?
Can the input 'edges' array be empty? If so, what should the function return?
Are the edges guaranteed to be within the range of valid team indices (0 to n-1)?
If no champion exists (e.g., a cyclic graph where every team loses to at least one other team), what should the function return?

Brute Force Solution

Approach

The brute force approach to finding the champion involves checking every possible pairing of teams. We directly simulate each tournament outcome to see which team would win. Essentially, we compare each team against every other team to see if it's a potential champion.

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

For each team, assume it's the potential champion.
Check if every other team loses to this potential champion based on the given results.
To do this, go through all the other teams one by one.
See if the result list shows that the potential champion beats that team.
If even one team doesn't lose to the potential champion, then that potential champion is not a real champion.
If, after checking all the other teams, we find that they all lose to the potential champion, then we've found a real champion.
Count how many teams are real champions according to this process.

Code Implementation

def find_champion_ii_brute_force(number_of_teams, results):
    number_of_champions = 0

    # Check each team to see if they are a champion
    for potential_champion in range(number_of_teams):
        is_champion = True

        # Iterate through all other teams to verify they lose to the potential champion
        for opponent_team in range(number_of_teams):
            if potential_champion == opponent_team:
                continue

            # Check if the opponent team loses to the potential champion according to the results
            loses_to_champion = False
            for result in results:
                if result[0] == potential_champion and result[1] == opponent_team:
                    loses_to_champion = True
                    break

            # If there's a team that doesn't lose to the potential champion, it's not a real champion
            if not loses_to_champion:
                is_champion = False
                break

        # Increment the champion count if the team is a real champion
        if is_champion:
            number_of_champions += 1

    return number_of_champions

Big(O) Analysis

Time Complexity

O(n²) – The provided solution iterates through each of the n teams, considering each as a potential champion. For each potential champion, it iterates through the remaining n-1 teams to check if the potential champion wins against them based on the input results. This nested loop structure leads to a time complexity proportional to n multiplied by (n-1). Therefore, the total number of operations approximates n * (n-1), which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm checks each team against every other team without using any significant extra data structures. It iterates through the results list and maintains a boolean flag to determine if a team is a champion. The space used is limited to a few variables for iteration and boolean flags, which remains constant regardless of the number of teams (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The problem identifies a tournament champion. Instead of simulating the entire tournament, we can use the idea that losers can't be champions. The key is to figure out how many players definitely lost at least one match.

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

Consider all the matches played. Each match has a winner and a loser.
Count how many players have lost at least one match. We can keep track of this count by looking at who lost in each game.
The champion is the player who has never lost. So, the champion is the only player that didn't lose at least once.
Subtract the number of losers from the total number of players. The result will be the number of players who never lost, which is our champion count. If the tournament has only one possible champion, that number will be one.

Code Implementation

def find_champion_ii(number_of_players, matches):
    losers = set()

    # Identify all players who have lost at least one match.
    for match in matches:
        loser = match[1]
        losers.add(loser)

    # Calculate the number of players who haven't lost.
    never_lost_count = number_of_players - len(losers)

    # If there's exactly one player who hasn't lost,
    if never_lost_count == 1:
        for player in range(number_of_players):
            # Then this is our champion.
            if player not in losers:
                return player
    
    # Otherwise, return -1 because there is no champion or many.
    return -1

Big(O) Analysis

Time Complexity

O(m) – The algorithm iterates through the given matches array. The number of matches is represented by 'm'. For each match, it identifies the loser and updates a set to track all losers. The size of the player set, 'n', does not directly influence the dominant cost since we always iterate through the matches. Therefore, the time complexity is directly proportional to the number of matches 'm'. The final subtraction is constant time.

Space Complexity

O(N) – The algorithm uses a set (or similar data structure) to keep track of the players who have lost at least one match. In the worst-case scenario, every player except one could have lost a match. Therefore, the set could potentially store up to N-1 losers, where N is the total number of players. This results in auxiliary space that grows linearly with the number of players. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty 'edges' list.	Return 0, as no champion can be determined without any edges.
An edge that refers to a non-existent node (out of range indices).	Handle this by either ignoring the edge or throwing an exception if the index is out of bounds for 'n'.
Self-loop edges (e.g., [0, 0]).	Ignore self-loop edges as a node cannot be defeated by itself.
Input 'n' is less than or equal to 0.	Return 0, as no valid champion can exist if there are no nodes.
Input 'edges' contains duplicate edges.	The indegree calculation handles this naturally by incrementing indegree multiple times.
Cyclic graph where every node defeats another; no single node with in-degree 0 exists.	Return -1 to indicate no champion exists in the cyclic graph.
Large input 'n' causing potential memory issues with indegree array.	Ensure the indegree array is initialized with the correct size relative to 'n', avoiding allocation errors.
Multiple nodes with an in-degree of zero (more than one potential champion).	Return -1 since there should be exactly one champion as per the problem definition.

Null or empty 'edges' list.

How to Handle:

Return 0, as no champion can be determined without any edges.

An edge that refers to a non-existent node (out of range indices).

How to Handle:

Handle this by either ignoring the edge or throwing an exception if the index is out of bounds for 'n'.

Self-loop edges (e.g., [0, 0]).

How to Handle:

Ignore self-loop edges as a node cannot be defeated by itself.

Input 'n' is less than or equal to 0.

How to Handle:

Return 0, as no valid champion can exist if there are no nodes.

Input 'edges' contains duplicate edges.

How to Handle:

The indegree calculation handles this naturally by incrementing indegree multiple times.

Cyclic graph where every node defeats another; no single node with in-degree 0 exists.

How to Handle:

Return -1 to indicate no champion exists in the cyclic graph.

Large input 'n' causing potential memory issues with indegree array.

How to Handle:

Ensure the indegree array is initialized with the correct size relative to 'n', avoiding allocation errors.

Multiple nodes with an in-degree of zero (more than one potential champion).

How to Handle:

Return -1 since there should be exactly one champion as per the problem definition.