Leetcode 2923: Find Champion I

Input: The input consists of a 2D boolean matrix grid where grid[i][j] indicates if team 'i' is stronger than team 'j'.

Example: For input grid = [[0, 1], [0, 0]], the result is 0.

Constraints:

• 2 <= n <= 100

• grid[i][j] is either 0 or 1

• grid[i][i] == 0

• For all i != j, grid[i][j] != grid[j][i]

Output: Return the index of the team that is the champion, or -1 if no such team exists.

Example: For input grid = [[0, 1], [0, 0]], the output is 0.

Constraints:

• The output will always be a valid team index or -1.

Goal: The goal is to find the team that no other team can beat, i.e., the team that has a '1' in every column of the matrix corresponding to the teams that it is stronger than.

Steps:

• Iterate through each row of the matrix.

• Sum the values in the row (excluding the diagonal).

• If the sum of a row equals n-1, that team is the champion.

Goal: The size of the grid will always match the number of teams, and it will adhere to the following constraints.

Steps:

• The number of teams, n, will always be between 2 and 100.

• Each row will contain exactly one 1 for every team the team is stronger than.

Assumptions:

• The grid matrix will always be valid and well-formed.

• Input: Example 1: grid = [[0, 1], [0, 0]]

• Explanation: Here, team 0 is stronger than team 1, and there are only two teams. Thus, team 0 will be the champion.

• Input: Example 2: grid = [[0, 0, 1], [1, 0, 1], [0, 0, 0]]

• Explanation: In this case, team 1 is stronger than both team 0 and team 2, making team 1 the champion.

Approach: To solve this problem, we need to identify the team that no other team can defeat. We can do this by summing the rows of the grid and checking if a row contains 'n-1' 1's.

Observations:

• The matrix represents a directed graph where each node (team) has directed edges (victories) to other teams.

• We are looking for a team that has outgoing edges to all other teams, and no other team has an outgoing edge to it.

Steps:

• Iterate through each team (row in the grid).

• Count the number of 1's in each row (excluding the diagonal).

• If the count equals n-1, return that team as the champion.

Empty Inputs:

• The input will never be empty.

Large Inputs:

• The algorithm must handle the grid size up to 100 x 100.

Special Values:

• When n = 2, there will be exactly one possible champion.

Constraints:

• The grid will always follow the rules as described in the problem.

int findChampion(vector<vector<int>>& g) {
    for (int i = 0; i < g.size(); ++i)
        if (accumulate(begin(g[i]), end(g[i]), 0) == g.size() - 1)
            return i;
    return -1;
}

1 : Function Definition

int findChampion(vector<vector<int>>& g) {

Defines the function 'findChampion' that takes a 2D vector 'g', which represents a directed graph, and returns the index of the champion node.

2 : Loop Over Graph

    for (int i = 0; i < g.size(); ++i)

Iterates through each row of the adjacency matrix 'g'. Each row represents a node in the graph, and we are checking if it is a potential champion.

3 : Check Champion Condition

        if (accumulate(begin(g[i]), end(g[i]), 0) == g.size() - 1)

Uses the 'accumulate' function to sum up the values in the current row of the matrix. A champion node should have all other nodes pointing to it, so the sum must be equal to 'g.size() - 1', indicating that all other nodes point to this node.

4 : Return Champion

            return i;

If the current node satisfies the champion condition, the function returns its index as the champion.

5 : Return No Champion

    return -1;

If no champion node is found after checking all rows, the function returns -1.

Best Case: O(n)

Average Case: O(n^2)

Worst Case: O(n^2)

Description: In the worst case, we will need to iterate through all teams and check each of their victories in the grid, leading to a time complexity of O(n^2).

Best Case: O(n)

Worst Case: O(n^2)

Description: We are storing the entire grid, which requires O(n^2) space.

Leetcode 2923: Find Champion I

Explore →