Find Champion I - Practice Coding Problems

Find Champion I - Problem

Array Matrix Easy

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.

Input & Output

Example 1 — Basic 3x3 Tournament

$ Input: grid = [[0,1,1],[1,0,1],[0,0,0]]

› Output: 0

💡 Note: Team 0 beats teams 1 and 2 (grid[0][1]=1, grid[0][2]=1). Team 1 beats team 2 (grid[1][2]=1). No team beats team 0, so team 0 is the champion.

Example 2 — Different Champion

$ Input: grid = [[0,0,1],[1,0,1],[0,0,0]]

› Output: 1

💡 Note: Team 1 beats teams 0 and 2. Team 0 beats team 2. No team beats team 1, so team 1 is the champion.

Example 3 — Small Tournament

$ Input: grid = [[0,1],[0,0]]

› Output: 0

💡 Note: Team 0 beats team 1 (grid[0][1]=1). No team beats team 0, making team 0 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] = 0

Visualization

Tap to expand

Understanding the Visualization

Input

Tournament grid where grid[i][j]=1 means team i beats team j

Process

Find team with no defeats (no incoming wins from others)

Output

Return the champion team number

Key Takeaway

🎯 Key Insight: The champion is the team that no other team defeats

Asked in

G Google 35 a Amazon 28 f Meta 22 M Microsoft 18

The key insight is that the champion is the team with no defeats. We can either check each team for defeats or count defeats per team. Best approach is counting defeats: Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Count Defeats Per Team	O(n²)	O(n)	Count how many times each team is defeated
Check Each Team	O(n²)	O(1)	For each team, check if any other team is stronger

Count Defeats Per Team — Algorithm Steps

Step 1: Initialize defeat counter for each team
Step 2: Scan grid and count defeats
Step 3: Find team with zero defeats

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create defeat counter for each team

Count

Scan grid and increment defeat counts

Find

Team with zero defeats is champion

Code -

solution.c — C

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

int solution(int** grid, int n) {
    int* defeats = (int*)calloc(n, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && grid[i][j] == 1) {
                defeats[j]++;
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (defeats[i] == 0) {
            free(defeats);
            return i;
        }
    }
    
    free(defeats);
    return -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small grids
    int n = 0;
    char* ptr = line;
    while (*ptr) {
        if (*ptr == '[' && *(ptr+1) != '[') n++;
        ptr++;
    }
    
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Parse values
    ptr = line;
    int row = 0, col = 0;
    while (*ptr && row < n) {
        if (*ptr >= '0' && *ptr <= '9') {
            grid[row][col] = *ptr - '0';
            col++;
            if (col == n) {
                col = 0;
                row++;
            }
        }
        ptr++;
    }
    
    int result = solution(grid, n);
    printf("%d\n", result);
    
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Single pass through n×n grid

⚠ Quadratic Growth

Space Complexity

O(n)

Array to store defeat count for each team

⚡ Linearithmic Space

25.4K Views

Medium Frequency

~15 min Avg. Time

892 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

Count Defeats Per Team — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler