Find Champion I

Easy

#2603Time: O(n^2), where `n` is the number of teams. In the worst-case scenario, we might have to check almost all pairs of teams. The outer loop runs up to `n` times, and the inner loop also runs `n` times.Space: O(1), as we only use a few variables to keep track of the loops and the defeated status, not dependent on the input size `n`.

Data structures

Array Matrix

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every team and checks if it meets the definition of a champion. A team is a champion if no other team is stronger than it. We can verify this for each team directly by checking if it has been defeated by any other team.

Algorithm

Iterate through each team i from 0 to n-1.
For each team i, assume it is not defeated by setting a flag, e.g., isDefeated = false.
Start a nested loop to iterate through every other team j from 0 to n-1.
If i is the same as j, skip the comparison.
Check if team j is stronger than team i by looking at grid[j][i]. If grid[j][i] == 1, it means team i is defeated. Set isDefeated = true and break the inner loop.
After the inner loop, if isDefeated is still false, it means no team could defeat team i. Thus, i is the champion. Return i.

Walkthrough

The algorithm systematically checks each team from 0 to n-1 to see if it's a champion. For a given team i, we iterate through all other teams j. If we find any team j that is stronger than team i (i.e., grid[j][i] == 1), we know that team i cannot be the champion. In this case, we can stop checking for team i and move on to the next potential champion, i+1. If we complete the inner loop for team i without finding any team that is stronger, it means team i is undefeated and is, therefore, the champion. The problem guarantees that a unique champion exists, so we can return i as soon as we find it.

1class Solution {2    public int findChampion(int[][] grid) {3        int n = grid.length;4        for (int i = 0; i < n; i++) {5            boolean isDefeated = false;6            for (int j = 0; j < n; j++) {7                if (i == j) {8                    continue;9                }10                // If team j is stronger than team i11                if (grid[j][i] == 1) {12                    isDefeated = true;13                    break; // Team i is not a champion, check next team14                }15            }16            // If after checking all other teams, no one defeated team i17            if (!isDefeated) {18                return i; // Team i is the champion19            }20        }21        return -1; // Should not be reached as a champion always exists22    }23}

Complexity

Time

O(n^2), where `n` is the number of teams. In the worst-case scenario, we might have to check almost all pairs of teams. The outer loop runs up to `n` times, and the inner loop also runs `n` times.

Space

O(1), as we only use a few variables to keep track of the loops and the defeated status, not dependent on the input size `n`.

Trade-offs

Pros

Straightforward and easy to understand, directly translating the problem definition into code.

Cons

Not the most efficient solution. The time complexity is quadratic, which can be slow for a very large number of teams (though acceptable for the given constraints).

A more efficient approach is to find the champion in a single pass. We can maintain a candidate for the champion and update it as we iterate through the teams. The key insight is that if a team i defeats our current candidate, the old candidate can be discarded, and i becomes the new candidate.

Algorithm

Initialize a variable championCandidate with the index of the first team, 0.
Iterate through the teams from i = 1 to n-1.
In each iteration, check if team i is stronger than the current championCandidate by checking grid[i][championCandidate].
If grid[i][championCandidate] == 1, update championCandidate to i.
After the loop completes, the value stored in championCandidate is the index of the champion team. Return championCandidate.

Walkthrough

This optimized algorithm leverages the transitivity property of the tournament (if a > b and b > c, then a > c). We start by assuming team 0 is the champion and store it in a championCandidate variable. Then, we iterate through the remaining teams from 1 to n-1. For each team i, we compare it with our current championCandidate.

If team i is stronger than championCandidate (i.e., grid[i][championCandidate] == 1), it means our current candidate is not the true champion. Team i is a better candidate, so we update championCandidate = i. Due to transitivity, any team that championCandidate was stronger than is also weaker than the new candidate i.
If team i is weaker than championCandidate, then i cannot be the champion, and we can safely discard it and keep our current championCandidate. After iterating through all the teams, the final championCandidate will be the one that was not defeated by any subsequent team in the pass. This process guarantees finding the single unique champion.

1class Solution {2    public int findChampion(int[][] grid) {3        int n = grid.length;4        int championCandidate = 0;5        for (int i = 1; i < n; i++) {6            // If team i is stronger than the current candidate7            if (grid[i][championCandidate] == 1) {8                // Team i becomes the new candidate9                championCandidate = i;10            }11        }12        return championCandidate;13    }14}

Complexity

Time

O(n), where `n` is the number of teams. We iterate through the list of teams only once.

Space

O(1), as we only use a single extra variable to store the champion candidate.

Trade-offs

Pros

Optimal time complexity, making it very fast.
Simple implementation with a single loop.

Cons

The correctness of the algorithm relies on the transitivity property of the tournament, which might not be immediately obvious without careful thought.

Solutions

Solution

1class Solution { public int findChampion ( int [][] grid ) { int n = grid . length ; for ( int i = 0 ;; ++ i ) { int cnt = 0 ; for ( int j = 0 ; j < n ; ++ j ) { if ( i != j && grid [ i ][ j ] == 1 ) { ++ cnt ; } } if ( cnt == n - 1 ) { return i ; } } } }

1class Solution { public: int findChampion ( vector < vector < int >>& grid ) { int n = grid . size (); for ( int i = 0 ;; ++ i ) { int cnt = 0 ; for ( int j = 0 ; j < n ; ++ j ) { if ( i != j && grid [ i ][ j ] == 1 ) { ++ cnt ; } } if ( cnt == n - 1 ) { return i ; } } } };

1class Solution : def findChampion ( self , grid : List [ List [ int ]]) -> int : for i , row in enumerate ( grid ): if all ( x == 1 for j , x in enumerate ( row ) if i != j ): return i

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem