Find Champion I

Find Champion I

What is this problem about?

The Find Champion I coding problem presents a tournament scenario represented by a grid. You are given an $n imes n$ matrix where grid[i][j] == 1 means team $i$ is stronger than team $j$, and grid[i][j] == 0 means otherwise. A "champion" is a team that is stronger than every other team in the tournament. You need to return the index of the champion team.

Why is this asked in interviews?

Google uses this question to test basic matrix traversal and logical deduction. It’s a test of "universal dominance." It evaluations whether you can correctly interpret a directed relationship matrix and identify the node that has an "out-degree" equal to $n-1$ (excluding itself). It’s also a test of your ability to handle edge cases, such as identifying if no champion exists.

Algorithmic pattern used

This problem uses a Linear Scan of the matrix rows.

1. For each row $i$:
   • Count how many 1s are in that row.
   • If the count is $n-1$, team $i$ has defeated everyone else.
2. Alternatively, since there is guaranteed to be a champion in version I, you can just find the team that has no one stronger than them (no 1s in their column).

Example explanation

Grid ($3 imes 3$):

[0, 1, 1]
[0, 0, 0]
[0, 1, 0]

1. Row 0: [0, 1, 1]. Count of 1s = 2. Since $2 = 3-1$, Team 0 is the champion.
2. Row 1: [0, 0, 0]. Count = 0.
3. Row 2: [0, 1, 0]. Count = 1. Result: 0.

Common mistakes candidates make

• Checking all pairs: Using a nested loop when a more efficient search is possible (though for a matrix, $O(N^2)$ is usually the baseline).
• Misinterpreting the diagonal: Forgetting that grid[i][i] is always 0 and doesn't count toward the dominance check.
• Symmetry errors: Assuming that if $i$ beats $j$, $j$ cannot beat $i$ (though the problem usually defines a tournament as directed).

Interview preparation tip

When dealing with "dominance" or "champions" in a matrix, think of it as finding a row of 1s or a column of 0s. This Matrix interview pattern is common in ranking and social network problems.