Find Champion I — Easy Problem & Solution

Problem statement

n teams play a CodeKairo tournament. grid[i][j] == 1 means team i is stronger than team j, and grid[j][i] == 0; every pair has exactly one winner, and grid[i][i] == 0.

The champion is the team no other team is stronger than. Return its index — it is guaranteed to be unique.

Example 1

Input: grid = [[0,1],[0,0]]
Output: 0
Explanation: Team 0 beats team 1, so nobody is above team 0.

Example 2

Input: grid = [[0,0,1],[1,0,1],[0,0,0]]
Output: 1
Explanation: Team 1 is stronger than both others.

Example 3

Input: grid = [[0]]
Output: 0

Constraints

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] is 0 or 1
• For all i, grid[i][i] == 0
• For all distinct i and j, exactly one of grid[i][j] and grid[j][i] is 1
• The champion is unique.

How to solve Find Champion I

Reading the matrix by column answers the question directly: column i holds a 1 at row j exactly when team j beats team i. The champion's column is therefore all zeros.

Approach

1. For each team i, scan column i.
2. If no other row holds a 1 there, i is the champion.

Why it works

Because every pair is decided and the champion is promised to exist and be unique, exactly one column is all zeros. Equivalently, the champion is the team with n - 1 wins in its own row — the two tests agree, and the column reading needs no count.

Complexity

• Time — O(n²)
• Space — O(1)

Pitfalls

• Scanning the row for all ones also works, but then the diagonal zero must be excluded from the count.
• grid[i][i] is always 0 and must not be read as a loss.
• The champion is an index, not a win count.

Reference solution

Python

from typing import List

def findChampion(grid: List[List[int]]) -> int:
    n = len(grid)
    for i in range(n):
        if all(grid[j][i] == 0 for j in range(n) if j != i):
            return i
    return -1

JavaScript

var findChampion = function(grid) {
    var n = grid.length;
    for (var i = 0; i < n; i++) {
        var beaten = false;
        for (var j = 0; j < n; j++) {
            if (j !== i && grid[j][i] === 1) beaten = true;
        }
        if (!beaten) return i;
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy