In a competitive tournament involving n participants indexed from 0 to n - 1, performence outcomes are represented by an n × n binary matrix. The entry at row i and column j indicates the direct comparison result between two participants. Specifically, if the value is 1, participant i outperforms participant j; otherwise, j is superior. A participant qualifies as the overall winner if no other participant consistently beats them.

Input Characteristics:

• An n × n integer matrix where diagonal entries are always 0.
• For any distinct pair i, j, exactly one of matrix[i][j] or matrix[j][i] is 1.
• The superiority relationship exhibits transitivity: if A defeats B and B defeats C, then A inevitably defeats C.

Objective: Return the index of the participant who remains undefeated across all comparisons.

Baseline Approach
A straightforward method involves scanning each row to verify whether it contains only a single 0 at the diagonal position, with all off-diagonal entries being 1. This requires examining every cell in the matrix, resulting in quadratic time complexity O(n²).

Optimized Linear Strategy
Leveraging the transitive property, the winner can be isolated in a single pass. We maintain a tracking variable representing the current strongest participant, initialized to index 0. As we iterate through the remaining participants, we compare each against the current tracker. If a new participant defeats the tracker, they immediate become the new candidate. Because transitivity guarantees that any participant already defeated by the current candidate cannot recover the top position, we safely discard previous candidates. After a single traversal completes, the tracking variable holds the index of the ultimate winner.

Implementation

#include <vector>

int findVictor(const std::vector<std::vector<int>>& matchupTable) {
    int reigningChampion = 0;
    for (size_t candidate = 1; candidate < matchupTable.size(); ++candidate) {
        if (matchupTable[candidate][reigningChampion] == 1) {
            reigningChampion = candidate;
        }
    }
    return reigningChampion;
}

Performance Evaluation
The algorithm executes exactly n - 1 pairwise checks, delivering a time complexity of O(n). Memory allocation remains constant at O(1) since the solution relies solely on a single integer variable for state tracking.