LeetCode 2923 - Find Champion I

This problem describes a tournament of n teams, where every pair of teams has a clear winner. The input is given as a square matrix called grid, where grid[i][j] tells us whether team i is stronger than team j.

leetcodeeasyarraymatrix

LeetCode Problem 2923

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Problem Understanding

This problem describes a tournament of n teams, where every pair of teams has a clear winner. The input is given as a square matrix called grid, where grid[i][j] tells us whether team i is stronger than team j.

If grid[i][j] == 1, then team i defeats team j, meaning i is stronger. Since the relationship is guaranteed to be one-directional, if grid[i][j] == 0, then grid[j][i] == 1, meaning team j is stronger than team i.

The goal is to find the champion, which is defined as the team that no other team is stronger than. In graph terminology, we want the node with zero incoming edges.

The problem also guarantees an important property:

If team a is stronger than team b, and team b is stronger than team c, then team a is stronger than team c.

This means the ranking is transitive, so the teams form a strict ordering. Because of this guarantee, there will always be exactly one champion.

The matrix has size n × n, where 2 <= n <= 100. Since n is very small, even an O(n²) solution is perfectly acceptable. However, understanding the tournament structure allows us to derive a cleaner and more elegant solution.

Several edge cases are worth considering upfront. The smallest possible input has only two teams, so the solution must correctly identify the stronger one. Another important case is when the champion appears later in the matrix rather than at index 0, which can expose flawed assumptions in naive implementations. Since the input guarantees a valid transitive ordering, we never need to worry about cycles or multiple champions.

Approaches

Brute Force Approach

A straightforward solution is to check every team and determine whether any other team is stronger than it.

For each team j, we inspect the entire column j of the matrix. If there exists some i such that grid[i][j] == 1, then team i is stronger than team j, meaning j cannot be the champion.

If we finish checking a team's column and find no stronger team, then that team is the champion.

This approach is correct because the champion is exactly the team with no incoming wins against it. By explicitly checking all possibilities, we guarantee correctness.

However, this requires scanning the matrix, leading to O(n²) time complexity.

Optimal Approach

The key observation is that we do not need to compare every team against every other team.

Suppose we maintain a current champion candidate.

Start with team 0 as the candidate. Then iterate through teams 1 to n - 1.

For each team i:

  • If grid[candidate][i] == 1, then the current candidate is stronger than i, so the candidate remains valid.
  • Otherwise, i is stronger than the current candidate, meaning the current candidate cannot be the champion. We replace the candidate with i.

Because of the transitive ordering guarantee, whenever a team defeats the current candidate, it automatically becomes a better champion candidate.

By the end of the traversal, only the real champion can survive.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Check every column to find a team with no stronger opponent
Optimal O(n) O(1) Maintain a running champion candidate

Algorithm Walkthrough

  1. Initialize a variable champion to 0.

We begin by assuming team 0 is the strongest team. This is only a temporary assumption and may change as we process the remaining teams. 2. Iterate through all remaining teams from 1 to n - 1.

Each team gets compared against the current champion candidate. 3. Compare the current candidate with the current team.

If grid[champion][team] == 1, then the current champion is stronger, so we keep it.

Otherwise, team is stronger than the current champion, meaning the current champion cannot possibly be the real champion. Update:

champion = team 4. Continue until all teams are processed.

Every comparison eliminates one impossible champion candidate. 5. Return the final value of champion.

By construction, this team must be stronger than every other remaining possibility.

Why it works

The crucial invariant is that after processing the first i teams, champion stores the only possible champion among those teams.

Whenever grid[champion][i] == 0, we know team i defeats the current candidate, so the candidate is eliminated forever. Due to transitivity, a defeated team can never become champion again.

Since every non-champion team eventually loses to someone stronger, only the true champion survives all eliminations.

Python Solution

from typing import List

class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        champion = 0
        n = len(grid)

        for team in range(1, n):
            if grid[champion][team] == 0:
                champion = team

        return champion

The implementation starts by assuming team 0 is the champion candidate.

We then iterate through all remaining teams. For each team, we check whether the current champion defeats it using grid[champion][team].

If the value is 1, the current champion remains stronger and stays unchanged.

If the value is 0, the current team defeats the champion candidate, so we update champion to the stronger team.

After all comparisons finish, the remaining candidate is returned as the answer.

The implementation uses only one integer variable to track the current best candidate, which keeps memory usage constant.

Go Solution

func findChampion(grid [][]int) int {
    champion := 0
    n := len(grid)

    for team := 1; team < n; team++ {
        if grid[champion][team] == 0 {
            champion = team
        }
    }

    return champion
}

The Go implementation follows the exact same logic as the Python version.

Since Go slices already provide efficient indexed access, no extra data structures are required. Integer overflow is not a concern because all indices are small and bounded by n <= 100.

The function assumes a valid square matrix as guaranteed by the problem constraints, so no defensive validation is necessary.

Worked Examples

Example 1

Input:

grid = [[0,1],
        [0,0]]

Initial state:

champion = 0
Step Team Comparison Result Champion
Start - Initial assumption Team 0 0
1 1 grid[0][1] = 1 Team 0 beats Team 1 0

Final answer:

0

Team 0 defeats team 1, so it remains champion.

Example 2

Input:

grid = [[0,0,1],
        [1,0,1],
        [0,0,0]]

Initial state:

champion = 0
Step Team Comparison Result Champion
Start - Initial assumption Team 0 0
1 1 grid[0][1] = 0 Team 1 beats Team 0 1
2 2 grid[1][2] = 1 Team 1 beats Team 2 1

Final answer:

1

Team 1 defeats both team 0 and team 2, making it the champion.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan through the teams once, performing one comparison per team
Space O(1) Only a single variable is used regardless of input size

The algorithm processes each team exactly once after initialization. Since every comparison removes one impossible candidate, only n - 1 comparisons are needed. No additional data structures are allocated, so the space complexity remains constant.

Test Cases

sol = Solution()

assert sol.findChampion([[0, 1], [0, 0]]) == 0  # Example 1

assert sol.findChampion([
    [0, 0, 1],
    [1, 0, 1],
    [0, 0, 0]
]) == 1  # Example 2

assert sol.findChampion([
    [0, 1],
    [0, 0]
]) == 0  # Smallest valid input, champion at index 0

assert sol.findChampion([
    [0, 0],
    [1, 0]
]) == 1  # Smallest valid input, champion at index 1

assert sol.findChampion([
    [0, 0, 0, 0],
    [1, 0, 0, 0],
    [1, 1, 0, 0],
    [1, 1, 1, 0]
]) == 3  # Champion appears at the end

assert sol.findChampion([
    [0, 1, 1, 1],
    [0, 0, 1, 1],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]) == 0  # Champion stays unchanged throughout

assert sol.findChampion([
    [0, 0, 0],
    [1, 0, 0],
    [1, 1, 0]
]) == 2  # Strict transitive ordering
Test Why
[[0,1],[0,0]] Validates the first provided example
[[0,0,1],[1,0,1],[0,0,0]] Validates the second provided example
Two teams, champion 0 Tests smallest valid input
Two teams, champion 1 Ensures champion is not assumed to be index 0
Champion at last index Ensures repeated candidate replacement works
Champion at first index Ensures candidate remains stable
Three-team transitive chain Validates transitive ordering assumptions

Edge Cases

One important edge case is the minimum input size, where n = 2. A careless implementation might accidentally skip comparisons or mishandle indexing. Since the algorithm always starts at index 1 and performs exactly one comparison, it works correctly even for the smallest valid matrix.

Another edge case occurs when the champion is not team 0. A naive implementation might incorrectly assume the first team remains strongest unless explicitly validated against everyone. Our implementation continuously replaces the champion candidate whenever a stronger team appears, ensuring the correct team is found regardless of position.

A third important case is when the champion appears near the end of the ordering. For example, in a strictly increasing strength hierarchy, the candidate changes repeatedly throughout the traversal. Since every comparison eliminates one impossible champion, the algorithm naturally converges to the strongest team by the final iteration.