Find Champion I - Solution & Explanation

Problem Overview: You are given an n x n tournament matrix where grid[i][j] = 1 means team i beats team j. The champion is the team that is not beaten by any other team. In graph terms, it is the node with zero incoming edges in a directed comparison matrix.

Approach 1: Naive Method with Grid Traversal (Time: O(n²), Space: O(1))

Scan the matrix column by column. If any grid[j][i] == 1, team j beats team i, so i cannot be the champion. For each team, iterate through all other teams and check if someone defeats it. The first team whose column contains only zeros (excluding itself) is the champion. This approach directly uses the tournament matrix representation and performs a full verification for every candidate.

The method is straightforward and mirrors the problem definition. However, it performs redundant checks because every candidate scans the entire column, leading to O(n^2) time. It works well for small inputs or when clarity is more important than micro‑optimizations.

Approach 2: Efficient Two-Pass Verification (Time: O(n), Space: O(1))

Instead of checking every team fully, eliminate non-champions while scanning once. Start with a candidate champ = 0. Iterate through teams from 1 to n-1. If grid[champ][i] == 0, the current champion loses to i, so update champ = i. Otherwise, i cannot be the champion because champ beats it.

After this pass, only one possible champion remains. Perform a second pass to verify that no team beats this candidate by checking grid[j][champ]. If all values are zero, the candidate is the champion. This technique treats the matrix like a directed comparison graph and progressively removes losing nodes.

The elimination idea avoids repeated scans and reduces the work to linear time. Only simple index comparisons are required, making the approach efficient even when the matrix is large. The underlying data structure is still a 2D array/matrix, but the algorithm behaves similarly to finding a node with zero in-degree in a graph.

Recommended for interviews: Start by explaining the naive column check because it directly models the problem definition. Then optimize using the two-pass elimination method. Interviewers usually expect the linear-time candidate elimination since it demonstrates reasoning about dominance relationships instead of brute-force scanning.