Scale Engineer

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
ArrayMatrix

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.

class Solution {    public int findChampion(int[][] grid) {        int n = grid.length;        for (int i = 0; i < n; i++) {            boolean isDefeated = false;            for (int j = 0; j < n; j++) {                if (i == j) {                    continue;                }                // If team j is stronger than team i                if (grid[j][i] == 1) {                    isDefeated = true;                    break; // Team i is not a champion, check next team                }            }            // If after checking all other teams, no one defeated team i            if (!isDefeated) {                return i; // Team i is the champion            }        }        return -1; // Should not be reached as a champion always exists    }}

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).

Solutions

class 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 ; } } } }

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 →

Next problem