Skip to main content
Talentd

Find Champion I - Solution & Explanation

EasyArrayMatrix15 min readAsked at: Google
Practice this problem

Problem Statement

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(n2), 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.

The solution utilizes nested for loops to evaluate each team's strength against others. The outer loop iterates through each team, considering it as a potential champion—subsequently, the inner loop checks if any other team is a stronger contender than the current team selection. If none are found, the current team is returned as the champion candidate.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2) due to the dual iteration over the grid.
Space Complexity: O(1) as no extra space is used apart from loop variables.

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.

The improved strategy involves firstly choosing a tentative champion through one full check against all others. The candidate is predicated on not yielding defeat against subsequent contenders. In final verification, the supposed champion is ensured of dominant status through complete bate array scrutiny.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) for candidate selection and another O(n) for validation, resulting in total O(n).
Space Complexity: O(1) as only variables for current index possession are needed, no additional data storage.

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Naive Method with Grid Traversal

Time Complexity: O(n^2) due to the dual iteration over the grid.
Space Complexity: O(1) as no extra space is used apart from loop variables.

Efficient Two-Pass Verification

Time Complexity: O(n) for candidate selection and another O(n) for validation, resulting in total O(n).
Space Complexity: O(1) as only variables for current index possession are needed, no additional data storage.

Enumeration—

Detailed Complexity Analysis

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

Video Solution

Leetcode | 2923. Find Champion I | Easy | Java Solution • Developer Docs • 754 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Find Champion I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays