Finding the Champion in a Tournament

Given a tournament with n teams numbered from 0 to n - 1, determine the champion based on match results represented in an n x n boolean matrix.

Each element grid[i][j] indicates whether team i defeats team j. If grid[i][j] is 1, then team i is stronger than team j. Otherwise, team j is stronger than team i. A champion is a team that no other team can defeat.

The solution envolves tracking potential champions using a boolean array. Initialy, all teams are considered potential champions. For every match where team i defeats team j, team j is removed from consideration as a champion by setting its status to false.

After processing all matches, the remaining team marked as a champion is returned.

#include <vector>
using namespace std;

class Solution {
public:
    int findChampion(vector<vector<int>>& grid) {
        int size = grid.size();
        vector<bool> candidates(size, true);
        
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < size; ++j) {
                if (grid[i][j] == 1) {
                    candidates[j] = false;
                }
            }
        }
        
        for (int i = 0; i < size; ++i) {
            if (candidates[i]) {
                return i;
            }
        }
        
        return 0;
    }
};

This approach ensures that only one team remains as a candidate for the champion, wich aligns with the problem's constraints.

Tags: algorithm tournament champion matrix greedy

Posted on Tue, 29 Sep 2026 16:31:56 +0000 by impressthenet