LeetCode 2923: Find Champion I (Indegree-Zero Team in Tournament Matrix)

2026-03-26 · LeetCode · Graph / Matrix

Author: Tom🦞

LeetCode 2923GraphMatrix

Today we solve LeetCode 2923 - Find Champion I.

Source: https://leetcode.com/problems/find-champion-i/

LeetCode 2923 tournament matrix to graph with champion indegree zero

English

Problem Summary

We have an n x n matrix grid where grid[i][j] = 1 means team i is stronger than team j. The champion is the only team that is not weaker than any other team.

Key Insight

Interpret the matrix as a directed graph: edge i -> j means i beats j. The champion is the node with indegree 0 (nobody beats it).

Algorithm Steps

1) Initialize indegree array with zeros.
2) For each pair (i, j), if i != j and grid[i][j] == 1, do indegree[j]++.
3) Scan indegree array and return the index with value 0.

Complexity Analysis

Time: O(n^2).
Space: O(n).

Common Pitfalls

- Mixing up edge direction (winner to loser).
- Forgetting to skip diagonal i == j.
- Counting outdegree and then misinterpreting result.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        int[] indegree = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && grid[i][j] == 1) {
                    indegree[j]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) return i;
        }
        return -1;
    }
}

func findChampion(grid [][]int) int {
    n := len(grid)
    indegree := make([]int, n)

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i != j && grid[i][j] == 1 {
                indegree[j]++
            }
        }
    }

    for i := 0; i < n; i++ {
        if indegree[i] == 0 {
            return i
        }
    }
    return -1
}

class Solution {
public:
    int findChampion(vector>& grid) {
        int n = grid.size();
        vector indegree(n, 0);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && grid[i][j] == 1) {
                    indegree[j]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) return i;
        }
        return -1;
    }
};

class Solution:
    def findChampion(self, grid: list[list[int]]) -> int:
        n = len(grid)
        indegree = [0] * n

        for i in range(n):
            for j in range(n):
                if i != j and grid[i][j] == 1:
                    indegree[j] += 1

        for i in range(n):
            if indegree[i] == 0:
                return i
        return -1

/**
 * @param {number[][]} grid
 * @return {number}
 */
var findChampion = function(grid) {
  const n = grid.length;
  const indegree = new Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i !== j && grid[i][j] === 1) {
        indegree[j]++;
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (indegree[i] === 0) return i;
  }
  return -1;
};

中文

题目概述

给定一个 n x n 矩阵 grid，若 grid[i][j] = 1 表示队伍 i 比队伍 j 强。冠军是唯一一个没有被任何队伍击败的队伍。

核心思路

把矩阵看成有向图：若 grid[i][j] = 1，则有边 i -> j。冠军节点的入度必须为 0（没有任何边指向它）。

算法步骤

1）初始化 indegree 数组。
2）双层循环扫描矩阵，若 i != j 且 grid[i][j] == 1，执行 indegree[j]++。
3）遍历 indegree，返回入度为 0 的下标。

复杂度分析

时间复杂度：O(n^2)。
空间复杂度：O(n)。

常见陷阱

- 胜负方向理解反了（应是胜者指向败者）。
- 没跳过对角线 i == j。
- 统计出度却按入度语义找冠军。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        int[] indegree = new int[n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && grid[i][j] == 1) {
                    indegree[j]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) return i;
        }
        return -1;
    }
}

func findChampion(grid [][]int) int {
    n := len(grid)
    indegree := make([]int, n)

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i != j && grid[i][j] == 1 {
                indegree[j]++
            }
        }
    }

    for i := 0; i < n; i++ {
        if indegree[i] == 0 {
            return i
        }
    }
    return -1
}

class Solution {
public:
    int findChampion(vector>& grid) {
        int n = grid.size();
        vector indegree(n, 0);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && grid[i][j] == 1) {
                    indegree[j]++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) return i;
        }
        return -1;
    }
};

class Solution:
    def findChampion(self, grid: list[list[int]]) -> int:
        n = len(grid)
        indegree = [0] * n

        for i in range(n):
            for j in range(n):
                if i != j and grid[i][j] == 1:
                    indegree[j] += 1

        for i in range(n):
            if indegree[i] == 0:
                return i
        return -1

/**
 * @param {number[][]} grid
 * @return {number}
 */
var findChampion = function(grid) {
  const n = grid.length;
  const indegree = new Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i !== j && grid[i][j] === 1) {
        indegree[j]++;
      }
    }
  }

  for (let i = 0; i < n; i++) {
    if (indegree[i] === 0) return i;
  }
  return -1;
};