2923. Find Champion I - Solution & Explanation

Q: Is Find Champion I easy or hard?

Find Champion I is classified as an Easy problem. The brute-force solution is straightforward with matrix traversal, and the optimized solution uses a simple elimination trick that reduces the complexity to O(n).

Q: Find Champion I Python/Java solution

A typical Python or Java solution either scans each column to find a team with no incoming wins or uses the O(n) elimination approach followed by verification. Both implementations rely on simple matrix indexing and constant extra memory.

Q: How to solve Find Champion I in O(n)?

Maintain a candidate champion and compare it with every other team once. If the candidate loses to team i (grid[candidate][i] == 0), update the candidate to i. After one pass, verify that no team beats the final candidate by checking its column. This requires only linear scans of the matrix indices.

Q: What is the best approach for Find Champion I?

The most efficient approach is the two-pass verification method. First eliminate non-champions by comparing teams sequentially, keeping only one possible candidate. Then verify that no team beats this candidate. This runs in O(n) time with O(1) extra space.

Q: Is Find Champion I asked at Google/Amazon/Meta?

Matrix comparison and tournament-style dominance problems appear in coding interviews at large tech companies, including Google, Amazon, and Meta. While this exact problem may vary, the underlying concept of eliminating candidates or finding nodes with zero in-degree is commonly tested.

Q: What data structure is used in Find Champion I?

The input is represented as a 2D matrix (or 2D array) where each cell indicates the result between two teams. Algorithmically, the matrix behaves like a directed graph adjacency matrix where the champion corresponds to a node with zero incoming edges.

Q: What is the time complexity of Find Champion I?

The straightforward matrix traversal solution runs in O(n^2) time because each team's column must be checked against all others. An optimized elimination approach reduces the complexity to O(n) by identifying a single candidate and verifying it once.

The problem

There are n teams numbered from 0 to n - 1 in a tournament.

Given a 0-indexed 2D boolean matrix grid of size n * n. For all i, j that 0 <= i, j <= n - 1 and i != j team i is stronger than team j if grid[i][j] == 1, otherwise, team j is stronger than team i.

Team a will be the champion of the tournament if there is no team b that is stronger than team a.

Return the team that will be the champion of the tournament.

Example 1:

Input: grid = [[0,1],[0,0]]
Output: 0
Explanation: There are two teams in this tournament.
grid[0][1] == 1 means that team 0 is stronger than team 1. So team 0 will be the champion.

Example 2:

Input: grid = [[0,0,1],[1,0,1],[0,0,0]]
Output: 1
Explanation: There are three teams in this tournament.
grid[1][0] == 1 means that team 1 is stronger than team 0.
grid[1][2] == 1 means that team 1 is stronger than team 2.
So team 1 will be the champion.

Constraints:

n == grid.length
n == grid[i].length
2 <= n <= 100
grid[i][j] is either 0 or 1.
For all i grid[i][i] is 0.
For all i, j that i != j, grid[i][j] != grid[j][i].
The input is generated such that if team a is stronger than team b and team b is stronger than team c, then team a is stronger than team c.

Approach overview

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.

Approach 1: Naive Method with Grid Traversal

In this approach, we iterate over each team and check if there exists another team that is not weaker against our current team in the grid matrix. The given constraints state that the grid is such that if grid[i][j] is 1, then grid[j][i] must be 0, ensuring transitive properties in ranking. We check each row in the grid and attempt to find any team that is stronger, and if found, we skip that candidate as a potential champion.

Python

def findChampion(grid):
    n = len(grid)
    for a in range(n):
        if all(grid[a][b] == 1 or a == b for b in range(n)):
            return a
    return -1  # The logic ensures we always find a champion

Java

class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        for (int a = 0; a < n; a++) {
            boolean isChampion = true;
            for (int b = 0; b < n; b++) {
                if (a != b && grid[b][a] == 1) {
                    isChampion = false;
                    break;
                }
            }
            if (isChampion) {
                return a;
            }
        }
        return -1; // According to problem constraints, shouldn't be reached
    }
}

C++

#include <vector>
using namespace std;

int findChampion(vector<vector<int>>& grid) {
    int n = grid.size();
    for (int a = 0; a < n; ++a) {
        bool isChampion = true;
        for (int b = 0; b < n; ++b) {
            if (a != b && grid[b][a] == 1) {
                isChampion = false;
                break;
            }
        }
        if (isChampion) {
            return a;
        }
    }
    return -1; // Should never happen
}

JavaScript

function findChampion(grid) {
    const n = grid.length;
    for (let a = 0; a < n; a++) {
        let isChampion = true;
        for (let b = 0; b < n; b++) {
            if (a !== b && grid[b][a] === 1) {
                isChampion = false;
                break;
            }
        }
        if (isChampion) {
            return a;
        }
    }
    return -1; // Should not occur as per problem statement
}

#include <stdbool.h>

int findChampion(int** grid, int n) {
    for (int a = 0; a < n; a++) {
        bool isChampion = true;
        for (int b = 0; b < n; b++) {
            if (a != b && grid[b][a] == 1) {
                isChampion = false;
                break;
            } 
        }
        if (isChampion) {
            return a;
        }
    }
    return -1; // Should never reach here based on problem constraints
}

public class Solution {
    public int FindChampion(int[][] grid) {
        int n = grid.Length;
        for (int a = 0; a < n; a++) {
            bool isChampion = true;
            for (int b = 0; b < n; b++) {
                if (a != b && grid[b][a] == 1) {
                    isChampion = false;
                    break;
                }
            }
            if (isChampion) {
                return a;
            }
        }
        return -1; // Unreachable
    }
}

Using Python's concise list comprehension and built-in functions, the solution checks for each team whether every other relevant comparison results in the current team 'a' being superior to team 'b'. If satisfied, 'a' is declared the champion.

Complexity

Time Complexity: O(n^2), stemming from each team's evaluation against all others.
Space Complexity: O(1), no additional data structures are utilized.

Try this approach in the editor

Approach 2: Efficient Two-Pass Verification

A two-pass approach can more efficiently find the champion by exploiting the grid's specific properties. Initially establish a candidate team that is assumed to be unchallenged based on unchecked comparisons. Post potential determination, a second pass verifiably checks whether this candidate truly remains unconquerable by random contingents.

Python

def findChampion(grid):
    n = len(grid)
    # First pass: find a champion candidate
    candidate = 0
    for b in range(1, n):
        if grid[candidate][b] == 0:
            candidate = b
    # Second pass: verify the candidate
    if all(grid[candidate][b] == 1 or candidate == b for b in range(n)):
        return candidate
    return -1

Java

class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        // Step 1: Identifying a possible champion
        int candidate = 0;
        for (int b = 1; b < n; b++) {
            if (grid[candidate][b] == 0) {
                candidate = b;
            }
        }
        // Step 2: Validation of the possible champion
        for (int b = 0; b < n; b++) {
            if (candidate != b && grid[b][candidate] == 1) {
                return -1;
            }
        }
        return candidate;
    }
}

C++

#include <vector>
using namespace std;

int findChampion(vector<vector<int>>& grid) {
    int n = grid.size();
    // Candidate finding
    int candidate = 0;
    for (int b = 1; b < n; ++b) {
        if (grid[candidate][b] == 0) {
            candidate = b;
        }
    }
    // Validation
    for (int b = 0; b < n; ++b) {
        if (candidate != b && grid[b][candidate] == 1) {
            return -1;
        }
    }
    return candidate;
}

JavaScript

function findChampion(grid) {
    const n = grid.length;
    // First pass to find champion candidate
    let candidate = 0;
    for (let b = 1; b < n; b++) {
        if (grid[candidate][b] === 0) {
            candidate = b;
        }
    }
    // Second pass to verify
    for (let b = 0; b < n; b++) {
        if (candidate !== b && grid[b][candidate] === 1) {
            return -1;
        }
    }
    return candidate;
}

#include <stdbool.h>

int findChampion(int** grid, int n) {
    // Step 1: Find a potential champion candidate
    int candidate = 0;
    for (int b = 1; b < n; b++) {
        if (grid[candidate][b] == 0) {
            candidate = b;
        }
    }
    // Step 2: Validate the candidate
    for (int b = 0; b < n; b++) {
        if (candidate != b && grid[b][candidate] == 1) {
            return -1; // Should not occur due to problem constraints
        }
    }
    return candidate;
}

public class Solution {
    public int FindChampion(int[][] grid) {
        int n = grid.Length;
        // First pass: identify a champion candidate
        int candidate = 0;
        for (int b = 1; b < n; b++) {
            if (grid[candidate][b] == 0) {
                candidate = b;
            }
        }
        // Second pass: verify the candidate
        for (int b = 0; b < n; b++) {
            if (candidate != b && grid[b][candidate] == 1) {
                return -1;
            }
        }
        return candidate;
    }
}

Extremely streamlined in language expressing predictance of the ultimate and guarantee against valiances amidst the remained columns, helping orchestrate succinct corroboration fulfilling.

Complexity

Time Complexity: O(n) for only limited necessary full matrix checks.
Space Complexity: O(1) given lack of additional resource insistence beyond iterators.

Try this approach in the editor

Approach 3: Enumeration

We can enumerate each team i. If team i has won every match, then team i is the champion, and we can directly return i.

The time complexity is O(n^2), where n is the number of teams. The space complexity is O(1).

TypeScript

function findChampion(grid: number[][]): number {
    for (let i = 0, n = grid.length; ; ++i) {
        let cnt = 0;
        for (let j = 0; j < n; ++j) {
            if (i !== j && grid[i][j] === 1) {
                ++cnt;
            }
        }
        if (cnt === n - 1) {
            return i;
        }
    }
}

func findChampion(grid [][]int) int {
	n := len(grid)
	for i := 0; ; i++ {
		cnt := 0
		for j, x := range grid[i] {
			if i != j && x == 1 {
				cnt++
			}
		}
		if cnt == n-1 {
			return i
		}
	}
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Naive Method with Grid Traversal	Time Complexity: O(n^2), stemming from each team's evaluation against all others. Space Complexity: O(1), no additional data structures are utilized.
Efficient Two-Pass Verification	Time Complexity: O(n) for only limited necessary full matrix checks. Space Complexity: O(1) given lack of additional resource insistence beyond iterators.
Enumeration	–

Complexity analysis

Approach	Time	Space	When to Use
Naive Method with Grid Traversal	O(n^2)	O(1)	Best for understanding the problem definition or when matrix size is small
Efficient Two-Pass Verification	O(n)	O(1)	Preferred in interviews and large inputs; eliminates non-champions in a single scan

Frequently asked questions

Is Find Champion I easy or hard?

Find Champion I is classified as an Easy problem. The brute-force solution is straightforward with matrix traversal, and the optimized solution uses a simple elimination trick that reduces the complexity to O(n).

Find Champion I Python/Java solution

A typical Python or Java solution either scans each column to find a team with no incoming wins or uses the O(n) elimination approach followed by verification. Both implementations rely on simple matrix indexing and constant extra memory.

How to solve Find Champion I in O(n)?

Maintain a candidate champion and compare it with every other team once. If the candidate loses to team i (grid[candidate][i] == 0), update the candidate to i. After one pass, verify that no team beats the final candidate by checking its column. This requires only linear scans of the matrix indices.

What is the best approach for Find Champion I?

The most efficient approach is the two-pass verification method. First eliminate non-champions by comparing teams sequentially, keeping only one possible candidate. Then verify that no team beats this candidate. This runs in O(n) time with O(1) extra space.

Is Find Champion I asked at Google/Amazon/Meta?

Matrix comparison and tournament-style dominance problems appear in coding interviews at large tech companies, including Google, Amazon, and Meta. While this exact problem may vary, the underlying concept of eliminating candidates or finding nodes with zero in-degree is commonly tested.

What data structure is used in Find Champion I?

The input is represented as a 2D matrix (or 2D array) where each cell indicates the result between two teams. Algorithmically, the matrix behaves like a directed graph adjacency matrix where the champion corresponds to a node with zero incoming edges.

What is the time complexity of Find Champion I?

The straightforward matrix traversal solution runs in O(n^2) time because each team's column must be checked against all others. An optimized elimination approach reduces the complexity to O(n) by identifying a single candidate and verifying it once.

Find Champion I solution and explanation

The problem

Approach overview

Approach 1: Naive Method with Grid Traversal

Approach 2: Efficient Two-Pass Verification

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Champion I solution and explanation

The problem

Approach overview

Approach 1: Naive Method with Grid Traversal

Approach 2: Efficient Two-Pass Verification

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems