2924. Find Champion II - Solution & Explanation

Q: 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.

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

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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] = [u_i, v_i] indicates that there is a directed edge from team u_i to team v_i 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 a₁, a₂, ..., a_n, a_n+1 such that node a₁ is the same node as node a_n+1, the nodes a₁, a₂, ..., a_n are distinct, and there is a directed edge from the node a_i to node a_i+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.

Python

def find_champion(n, edges):
    in_degree = [0] * n
    for u, v in edges:
        in_degree[v] += 1
    champion = -1
    for i in range(n):
        if in_degree[i] == 0:
            if champion == -1:
                champion = i
            else:
                return -1
    return champion

print(find_champion(3, [[0, 1], [1, 2]]))

Java

import java.util.*;

public class Tournament {
    public static int findChampion(int n, int[][] edges) {
        int[] inDegree = new int[n];
        for (int[] edge : edges) {
            inDegree[edge[1]]++;
        }
        int champion = -1;
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                if (champion == -1) {
                    champion = i;
                } else {
                    return -1;
                }
            }
        }
        return champion;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {1, 2}};
        int result = findChampion(3, edges);
        System.out.println("Champion: " + result);
    }
}

C++

#include <iostream>
#include <vector>

int findChampion(int n, const std::vector<std::pair<int, int>>& edges) {
    std::vector<int> inDegree(n, 0);
    for (const auto& edge : edges) {
        inDegree[edge.second]++;
    }
    int champion = -1;
    for (int i = 0; i < n; ++i) {
        if (inDegree[i] == 0) {
            if (champion == -1) {
                champion = i;
            } else {
                return -1;
            }
        }
    }
    return champion;
}

int main() {
    std::vector<std::pair<int, int>> edges = {{0, 1}, {1, 2}};
    int result = findChampion(3, edges);
    std::cout << "Champion: " << result << std::endl;
    return 0;
}

JavaScript

function findChampion(n, edges) {
    let inDegree = new Array(n).fill(0);
    for (let [u, v] of edges) {
        inDegree[v]++;
    }
    let champion = -1;
    for (let i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            if (champion === -1) {
                champion = i;
            } else {
                return -1;
            }
        }
    }
    return champion;
}

console.log(findChampion(3, [[0, 1], [1, 2]]));

#include <stdio.h>
#include <stdbool.h>

int findChampion(int n, int edges[][2], int edgesSize) {
    int inDegree[n];
    for (int i = 0; i < n; i++) inDegree[i] = 0;
    
    for (int i = 0; i < edgesSize; i++) {
        inDegree[edges[i][1]]++;
    }
    
    int champion = -1;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            if (champion == -1) {
                champion = i;
            } else {
                return -1; // More than one champion
            }
        }
    }
    return champion;
}

int main() {
    int edges[][2] = {{0, 1}, {1, 2}};
    int result = findChampion(3, edges, 2);
    printf("Champion: %d\n", result);
    return 0;
}

using System;

public class Tournament {
    public static int FindChampion(int n, int[][] edges) {
        int[] inDegree = new int[n];
        foreach (var edge in edges) {
            inDegree[edge[1]]++;
        }
        int champion = -1;
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                if (champion == -1) {
                    champion = i;
                } else {
                    return -1;
                }
            }
        }
        return champion;
    }

    public static void Main() {
        int[][] edges = { new int[] { 0, 1 }, new int[] { 1, 2 } };
        Console.WriteLine("Champion: " + FindChampion(3, edges));
    }
}

In this Python solution, we use a list to count in-degrees, then it checks for nodes with zero in-degrees, identifying a single such node as the champion if one exists.

Complexity

Time Complexity: O(n + m). Space Complexity: O(n).

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.

Python

def topological_sort(n, adj):
    visited = [False] * n
    stack = []
    def dfs(v):
        visited[v] = True
        for i in adj[v]:
            if not visited[i]:
                dfs(i)
        stack.append(v)

    for i in range(n):
        if not visited[i]:
            dfs(i)
    return stack


def find_champion(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    stack = topological_sort(n, adj)
    potential_champion = stack[-1]
    for team in stack[:-1]:
        if potential_champion not in adj[team]:
            return -1
    return potential_champion

print(find_champion(3, [[0, 1], [1, 2]]))

Java

import java.util.*;

public class Tournament {
    private static void topologicalSortUtil(int v, boolean[] visited, Stack<Integer> stack, List<List<Integer>> adj) {
        visited[v] = true;
        for (int i : adj.get(v)) {
            if (!visited[i])
                topologicalSortUtil(i, visited, stack, adj);
        }
        stack.push(v);
    }

    public static int findChampion(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
        }
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i])
                topologicalSortUtil(i, visited, stack, adj);
        }
        int potentialChampion = stack.pop();
        while (!stack.isEmpty()) {
            if (!adj.get(potentialChampion).contains(stack.peek()))
                return -1;
            stack.pop();
        }
        return potentialChampion;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {1, 2}};
        int result = findChampion(3, edges);
        System.out.println("Champion: " + result);
    }
}

C++

#include <iostream>
#include <vector>
#include <stack>

void topologicalSortUtil(int v, std::vector<bool>& visited, std::stack<int>& Stack, const std::vector<std::vector<int>>& adj) {
    visited[v] = true;
    for (int i : adj[v]) {
        if (!visited[i])
            topologicalSortUtil(i, visited, Stack, adj);
    }
    Stack.push(v);
}

int findChampion(int n, const std::vector<std::pair<int, int>>& edges) {
    std::vector<std::vector<int>> adj(n);
    for (const auto& edge : edges) {
        adj[edge.first].push_back(edge.second);
    }
    std::stack<int> Stack;
    std::vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i])
            topologicalSortUtil(i, visited, Stack, adj);
    }
    int potentialChampion = Stack.top();
    Stack.pop();
    while (!Stack.empty()) {
        if (std::find(adj[potentialChampion].begin(), adj[potentialChampion].end(), Stack.top()) == adj[potentialChampion].end())
            return -1;
        Stack.pop();
    }
    return potentialChampion;
}

int main() {
    std::vector<std::pair<int, int>> edges = {{0, 1}, {1, 2}};
    int result = findChampion(3, edges);
    std::cout << "Champion: " << result << std::endl;
    return 0;
}

JavaScript

function topologicalSort(n, adj) {
    let visited = new Array(n).fill(false);
    let stack = [];

    function dfs(v) {
        visited[v] = true;
        for (let i of adj[v]) {
            if (!visited[i]) {
                dfs(i);
            }
        }
        stack.push(v);
    }

    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    return stack;
}

function findChampion(n, edges) {
    let adj = Array.from({ length: n }, () => []);
    for (let [u, v] of edges) {
        adj[u].push(v);
    }
    let stack = topologicalSort(n, adj);
    let potentialChampion = stack.pop();

    for (let team of stack) {
        if (!adj[potentialChampion].includes(team))
            return -1;
    }
    return potentialChampion;
}

console.log(findChampion(3, [[0, 1], [1, 2]]));

#include <stdio.h>
#include <stdlib.h>

void topologicalSortUtil(int v, int visited[], int *stack, int *index, int adj[][100], int n) {
    visited[v] = 1;
    for (int i = 0; i < n; i++) {
        if (adj[v][i] && !visited[i]) {
            topologicalSortUtil(i, visited, stack, index, adj, n);
        }
    }
    stack[(*index)--] = v;
}

int topologicalSort(int n, int edges[][2], int edgesSize) {
    int adj[100][100] = {0};
    for (int i = 0; i < edgesSize; i++) {
        adj[edges[i][0]][edges[i][1]] = 1;
    }
    int visited[100] = {0};
    int stack[100];
    int index = n - 1;
    for (int i = 0; i < n; i++) {
        if (!visited[i])
            topologicalSortUtil(i, visited, stack, &index, adj, n);
    }
    int potentialChampion = stack[n - 1];
    for (int i = 0; i < n - 1; i++) {
        if (!adj[potentialChampion][stack[i]])
            return -1;
    }
    return potentialChampion;
}

int main() {
    int edges[][2] = {{0, 1}, {1, 2}};
    int result = topologicalSort(3, edges, 2);
    printf("Champion: %d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;

public class Tournament {
    private static void TopologicalSortUtil(int v, bool[] visited, Stack<int> stack, List<List<int>> adj) {
        visited[v] = true;
        foreach (int i in adj[v]) {
            if (!visited[i])
                TopologicalSortUtil(i, visited, stack, adj);
        }
        stack.Push(v);
    }

    public static int FindChampion(int n, int[][] edges) {
        List<List<int>> adj = new List<List<int>>(n);
        for (int i = 0; i < n; i++) adj.Add(new List<int>());
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
        }
        Stack<int> stack = new Stack<int>();
        bool[] visited = new bool[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i])
                TopologicalSortUtil(i, visited, stack, adj);
        }
        int potentialChampion = stack.Pop();
        foreach (int team in stack) {
            if (!adj[potentialChampion].Contains(team))
                return -1;
        }
        return potentialChampion;
    }

    public static void Main() {
        int[][] edges = { new int[] { 0, 1 }, new int[] { 1, 2 } };
        Console.WriteLine("Champion: " + FindChampion(3, edges));
    }
}

In Python, this solution leverages a DFS-based topological sort and checks if the final level node in the sort order implies a single champion if valid.

Complexity

Time Complexity: O(n + m). Space Complexity: O(n).

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.

TypeScript

function findChampion(n: number, edges: number[][]): number {
    const indeg: number[] = Array(n).fill(0);
    for (const [_, v] of edges) {
        ++indeg[v];
    }
    let [ans, cnt] = [-1, 0];
    for (let i = 0; i < n; ++i) {
        if (indeg[i] === 0) {
            ++cnt;
            ans = i;
        }
    }
    return cnt === 1 ? ans : -1;
}

func findChampion(n int, edges [][]int) int {
	indeg := make([]int, n)
	for _, e := range edges {
		indeg[e[1]]++
	}
	ans, cnt := -1, 0
	for i, x := range indeg {
		if x == 0 {
			cnt++
			ans = i
		}
	}
	if cnt == 1 {
		return ans
	}
	return -1
}

Try this approach in the editor

Approach 4: Default Approach

TypeScript

function findChampion(n: number, edges: number[][]): number {
    const vertexes = new Set<number>(Array.from({ length: n }, (_, i) => i));

    for (const [_, v] of edges) {
        vertexes.delete(v);
    }

    return vertexes.size === 1 ? vertexes[Symbol.iterator]().next().value! : -1;
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
In-degree Tracking	Time Complexity: O(n + m). Space Complexity: O(n).
Topological Sorting	Time Complexity: O(n + m). Space Complexity: O(n).
Counting In-degrees	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
In-degree Tracking	O(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

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.

Find Champion II solution and explanation

The problem

Approach overview

Approach 1: In-degree Tracking

Approach 2: Topological Sorting

Approach 3: Counting In-degrees

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find Champion II solution and explanation

The problem

Approach overview

Approach 1: In-degree Tracking

Approach 2: Topological Sorting

Approach 3: Counting In-degrees

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems