DDSA Solutions

2924. Find Champion II

MediumView on LeetCode
Graph
Time: O(n + E)
Space: O(n)

Problem Overview

Find champion in tournament DAG: node with in-degree 0.

Intuition

Find champion in tournament DAG: node with in-degree 0. Only one team can beat all others.

Algorithm

  1. 1Compute in-degrees. Return the single node with in-degree 0. If multiple: return -1.

Common Pitfalls

  • •Champion has in-degree 0. If multiple nodes have in-degree 0: no unique champion, return -1.
2924.cs
C#
// Approach: Find node with in-degree 0; if exactly one exists it is the champion, else return -1.
// Time: O(n + E) Space: O(n)

public class Solution
{
    public int FindChampion(int n, int[][] edges)
    {
        int ans = -1;
        int count = 0;
        int[] inDegrees = new int[n];

        foreach (var edge in edges)
        {
            int v = edge[1];
            ++inDegrees[v];
        }

        for (int i = 0; i < n; ++i)
        {
            if (inDegrees[i] == 0)
            {
                ++count;
                ans = i;
            }
        }

        return count > 1 ? -1 : ans;
    }
}
Was this solution helpful?

Related Problems