Find Champion I

Easy
929.

Find Champion I

Find Champion I is an easy coding problem on arrays, matrix and graph, asked in Amazon, Google and Infosys interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var findChampion = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Champion I — Solution in Python, Java & C++

Find Champion I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and matrix.

Find Champion I is an easy coding problem on arrays, matrix and graph, asked in Amazon, Google and Infosys interviews.

  • Difficulty: Easy
  • Topics: Arrays, Matrix, Graph
  • Asked at: Amazon, Google, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Find Champion I

  1. Hint 1

    A team is the champion when nothing beats it.

  2. Hint 2

    Column i records who is stronger than team i.

  3. Hint 3

    So look for the column that is all zeros.

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

Java

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

C++

int findChampion(vector<vector<int>>& grid) {
    int n = (int) grid.size();
    for (int i = 0; i < n; i++) {
        bool beaten = false;
        for (int j = 0; j < n; j++) {
            if (j != i && grid[j][i] == 1) beaten = true;
        }
        if (!beaten) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal