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.