Find Champion II Solution in Java

Explore Solutions in Other Languages

Problem Description

Welcome to the world of competitive programming, where finding a champion is as easy as finding a needle in a haystack—if that needle was also hiding from you! The problem at hand, Find Champion II, is like a game of hide and seek, but instead of kids, we have nodes in a directed graph.

Imagine a group of friends (nodes) where some of them are connected (edges) by a friendship (directed edge). The goal is to find a “champion” friend who has no one pointing at them (in-degree of zero). If there are multiple friends with no one pointing at them, well, sorry, you can’t have a champion; it’s a tie!

In simpler terms, if you think of a party where everyone is gossiping about someone, the champion is the one who is not being gossiped about. If two or more people are not being gossiped about, then it’s a chaotic party, and we can’t crown a champion!

Code Solution


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

    for (int[] edge : edges) {
      final 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;
  }
}

Approach Explanation

The approach here is straightforward: we maintain an array to count the in-degrees of each node. We iterate through the edges to populate this array. After that, we check which nodes have an in-degree of zero. If we find more than one such node, we return -1, indicating that there is no unique champion. Otherwise, we return the index of the champion.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n + m)
Space Complexity	O(n)

Real-World Example

Think of a school where students (nodes) are connected by friendships (edges). If you want to find the most popular student (champion) who has no one disliking them (in-degree of zero), you can use this algorithm. If two students are equally liked and have no dislikers, then it’s a popularity contest gone wrong!