Skip to main content
Talentd

Find Champion II - Solution & Explanation

MediumGraph19 min readAsked at: Meta, Google
Practice this problem

Problem Statement

There are n teams numbered from 0 to n - 1 in a tournament; each team is also a node in a DAG.

You are given the integer n and a 0-indexed 2D integer array edges of length m representing the DAG, where edges[i] = [ui, vi] indicates that there is a directed edge from team ui to team vi in the graph.

A directed edge from a to b in the graph means that team a is stronger than team b and team b is weaker than team a.

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 if there is a unique champion, otherwise, return -1.

Notes

  • A cycle is a series of nodes a1, a2, ..., an, an+1 such that node a1 is the same node as node an+1, the nodes a1, a2, ..., an are distinct, and there is a directed edge from the node ai to node ai+1 for every i in the range [1, n].
  • A DAG is a directed graph that does not have any cycle.

 

Example 1:

Input: n = 3, edges = [[0,1],[1,2]]
Output: 0
Explanation: Team 1 is weaker than team 0. Team 2 is weaker than team 1. So the champion is team 0.

Example 2:

Input: n = 4, edges = [[0,2],[1,3],[1,2]]
Output: -1
Explanation: Team 2 is weaker than team 0 and team 1. Team 3 is weaker than team 1. But team 1 and team 0 are not weaker than any other teams. So the answer is -1.

 

Constraints:

  • 1 <= n <= 100
  • m == edges.length
  • 0 <= m <= n * (n - 1) / 2
  • edges[i].length == 2
  • 0 <= edge[i][j] <= n - 1
  • edges[i][0] != edges[i][1]
  • The input is generated such that if team a is stronger than team b, team b is not stronger than team a.
  • 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 n teams and a list of directed edges where [a, b] means team a beats team b. The champion is the only team that no other team beats. In graph terms, this is the node with zero incoming edges. If more than one such node exists, or none exists, there is no clear champion and the result is -1.

Approach 1: In-degree Tracking (O(n + m) time, O(n) space)

Treat the input as a directed graph with n nodes and m edges. Maintain an array indegree[n] initialized to zero. Iterate through every edge (u, v) and increment indegree[v]. After processing all edges, scan the array to count how many nodes have indegree == 0. If exactly one node has zero incoming edges, that node is the champion because no other team defeated it. If the count is greater than one or zero, return -1. This works because every defeated team must have at least one incoming edge. The approach is linear in the size of the graph and uses only a single pass over edges plus a scan of nodes. This is the simplest and most direct solution when working with a graph representation.

Approach 2: Topological Sorting (O(n + m) time, O(n + m) space)

Another way to reason about the champion is through topological sorting. Build an adjacency list and compute the in-degree of each node. Push every node with indegree == 0 into a queue. If more than one node enters the queue initially, multiple teams are undefeated and a unique champion does not exist. Otherwise, process nodes in topological order by removing them from the queue and reducing the in-degree of their neighbors. The first node processed represents the only node with zero incoming edges at the start, which identifies the champion candidate. If the initial queue contains more than one node, return -1. This approach mirrors standard graph traversal workflows used in DAG processing and is useful when you already need the graph structure for further processing.

Recommended for interviews: The in-degree tracking solution is what interviewers usually expect. It shows you understand how directed graphs encode dominance relationships and how to identify source nodes efficiently. Topological sorting demonstrates deeper graph knowledge, but it introduces extra structures that are unnecessary for this specific problem. Showing the simple in-degree observation first and then mentioning the topological sort interpretation signals strong problem-solving clarity.

Approach 1: In-degree Tracking

In this approach, we calculate the in-degree for each node in the graph. The in-degree of a node is the number of edges that point to it. If a node has an in-degree of 0, it means no other node (team in this case) is stronger than it, making it a candidate for the champion. If exactly one such node exists, it is the unique champion. Otherwise, we return -1.

This C code snippet creates an array to store the in-degree of each team. It iterates over the edges, updating the in-degree of destination nodes. Finally, it checks for nodes with an in-degree of 0. If there's exactly one, it returns this as the champion.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges. Space Complexity: O(n), as we store the in-degree of each node.

Try this approach in the editor →

Approach 2: Topological Sorting

This approach uses topological sorting to find the last node in the order, presuming no other nodes are stronger. If multiple final nodes exist in the topological order, it implies multiple candidates, hence no unique champion can be determined.

This C implementation uses DFS for topological sorting to find the potential champion, verifying it by checking if it's stronger than all other remaining teams.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m). Space Complexity: O(n^2) due to adjacency matrix used for simplicity.

Try this approach in the editor →

Approach 3: Counting In-degrees

Based on the problem description, we only need to count the in-degrees of each node and record them in an array indeg. If only one node has an in-degree of 0, then this node is the champion; otherwise, there is no unique champion.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Approach 4: Default Approach

Code

TypeScriptJavaScript

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
In-degree Tracking

Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges. Space Complexity: O(n), as we store the in-degree of each node.

Topological Sorting

Time Complexity: O(n + m). Space Complexity: O(n^2) due to adjacency matrix used for simplicity.

Counting In-degrees—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
In-degree TrackingO(n + m)O(n)Best general solution when you only need to identify the node with zero incoming edges
Topological Sorting (Kahn's Algorithm)O(n + m)O(n + m)Useful when performing broader DAG processing or when topological order is also required

Video Solution

Find Champion II - Leetcode 2924 - Python • NeetCodeIO • 6,776 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Champion II easy or hard?
Find Champion II is generally considered a medium-level problem. The implementation is simple once you recognize the graph pattern, but identifying that the champion corresponds to the only node with zero in-degree requires familiarity with directed graph concepts.
How to solve Find Champion II in O(n)?
Treat the teams as nodes in a directed graph and track the in-degree of each node. Iterate through the edges and increment the in-degree of the destination node. After processing all edges, scan for nodes with in-degree 0. If exactly one exists, return it; otherwise return -1. The overall complexity is O(n + m).
Find Champion II Python or Java solution?
The logic is identical across languages: compute an in-degree array, process all edges, then find the single node with zero in-degree. This can be implemented in Python, Java, C++, JavaScript, C#, and C using simple arrays and loops.
What is the best approach for Find Champion II?
The most efficient approach is in-degree tracking. Build an array counting incoming edges for each node and identify the node with indegree 0. If exactly one such node exists, it is the champion. The algorithm runs in O(n + m) time and O(n) space, where m is the number of edges.
Is Find Champion II asked at Google/Amazon/Meta?
Problems involving graph sources, in-degree counting, and topological sorting frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the underlying pattern of identifying nodes with zero in-degree in a directed graph is very common.
What data structure is used in Find Champion II?
The solution primarily uses arrays (or lists) to track in-degrees and optionally an adjacency list for graph representation. If using topological sorting, a queue is also used to process nodes with zero in-degree.
What is the time complexity of Find Champion II?
Both common solutions run in O(n + m) time, where n is the number of teams and m is the number of match results (edges). Each edge is processed once to compute in-degrees, and the nodes are scanned once to find the zero in-degree candidate.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Clone Graph

Next

Course Schedule