Intuition

The problem revolves around identifying a "champion" in a Directed Acyclic Graph (DAG) based on specific rules.

Approach

1. Tracking Defeated Teams:
2. Use a bitset of size 100 to track teams that have been defeated (i.e., have incoming edges).
3. For every directed edge [u, v], mark v in the losses bitset, as it indicates that v has been defeated by u.
4. Identifying the Champion:
5. Iterate through all n teams.
6. If a team i has not been defeated (losses[i] == false), it is a potential champion.
7. If more than one such team is found, return -1 immediately, as there is no unique champion.
8. Return the Result:
9. If exactly one team has no incoming edges, its index is returned as the champion.
10. If all teams have been defeated, champion remains -1, and the function returns -1.

Complexity

• Time complexity: O(m+n)
• Marking defeated teams O(m), where m is the number of edges (size of edges).

• Checking all teams O(n), where n is the number of teams.

• Space complexity: O(n)

Code

class Solution {
public:
    int findChampion(int n, vector<vector<int>>& edges) {
        bitset<100> losses; 
        for (const auto& edge : edges) {
            losses.set(edge[1]);
        }
        int champion = -1;
        for (int i = 0; i < n; i++) {
            if (!losses[i]) {
                if (champion != -1) return -1;
                champion = i;
            }
        }
        return champion;
    }
};