Find Champion II - Practice Coding Problems

Find Champion II - Problem

Graph Medium

There are n teams numbered from 0 to n - 1 in a tournament; each team is also a node in a DAG (Directed Acyclic Graph). 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.

Input & Output

Example 1 — Basic Tournament

$ Input: n = 3, edges = [[0,1],[1,2]]

› Output: 0

💡 Note: Team 0 beats team 1, team 1 beats team 2. Team 0 has no incoming edges, so it's the unique champion.

Example 2 — No Unique Champion

$ Input: n = 4, edges = [[0,2],[1,3],[1,2]]

› Output: -1

💡 Note: Both team 0 and team 1 have no incoming edges, so there's no unique champion.

Example 3 — Single Team

$ Input: n = 1, edges = []

› Output: 0

💡 Note: Only one team exists with no edges, so team 0 is the champion by default.

Constraints

1 ≤ n ≤ 100
0 ≤ edges.length ≤ 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

Visualization

Tap to expand

Understanding the Visualization

Input Graph

n=3 teams with edges [[0,1],[1,2]]

Count In-degrees

Team 0: 0, Team 1: 1, Team 2: 1

Find Champion

Team 0 has unique zero in-degree

Key Takeaway

🎯 Key Insight: The champion is the unique team with zero incoming edges (in-degree = 0)

Asked in

a Amazon 15 M Microsoft 12

The key insight is that the champion has zero incoming edges (no team beats them). Best approach uses in-degree counting for O(n + m) time and O(n) space efficiency.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Check	O(n*m)	O(1)	For each team, check if any other team defeats it
In-degree Counting	O(n + m)	O(n)	Count incoming edges for each team in a single pass

Brute Force Check — Algorithm Steps

Step 1: For each team from 0 to n-1
Step 2: Check all edges to see if any edge points to this team
Step 3: If exactly one team has no incoming edges, return it

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Team 0

Scan all edges to see if any point to team 0

Check Team 1

Scan all edges to see if any point to team 1

Find Champion

The team with no incoming edges is champion

Code -

solution.c — C

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

int solution(int n, int edges[][2], int edgeCount) {
    int championCount = 0;
    int champion = -1;
    
    for (int team = 0; team < n; team++) {
        int hasIncoming = 0;
        for (int i = 0; i < edgeCount; i++) {
            if (edges[i][1] == team) {
                hasIncoming = 1;
                break;
            }
        }
        
        if (!hasIncoming) {
            championCount++;
            champion = team;
        }
    }
    
    return championCount == 1 ? champion : -1;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Parse edges manually
    int edges[1000][2];
    int edgeCount = 0;
    
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            edges[edgeCount][0] = strtol(ptr, &ptr, 10);
            ptr++; // Skip comma
            edges[edgeCount][1] = strtol(ptr, &ptr, 10);
            edgeCount++;
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr) ptr++;
        } else {
            ptr++;
        }
    }
    
    int result = solution(n, edges, edgeCount);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n*m)

For each of n teams, we scan all m edges

✓ Linear Growth

Space Complexity

O(1)

Only using counter variables

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

486 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler