Free lessonsGraphs · Stage 0 · Edges and neighbours · Step 4

Everyone follows them

With one-way edges, count arrows in and arrows out separately. About 10 minutes.

Two counts per person

With arrows, "how connected is this person?" splits into two questions. How many arrows point at them? Those are their followers. How many arrows leave them? That is how many people they follow.

Read each arrow once: it leaves the person who follows, and lands on the person being followed. So one pass over the arrows gives both counts.

The arrow leaves: the follower's following count goes up.

The arrow lands: the followed person's follower count goes up.

In code

followers = [0] * n
following = [0] * n
for a, b in follows:
    following[a] += 1
    followers[b] += 1
for person in range(n):
    if followers[person] != n - 1:
        continue
    if following[person] == 0:
        return person
return -1

4 people, follows [[0, 3], [1, 3], [2, 3], [0, 1], [2, 0]]

Four people. Under each one: arrows in (followers) and arrows out (following). All zero so far.

Move 1 of 5

Spotting the influencer

An influencer is followed by everyone else, which is n minus 1 followers, and follows nobody. Both conditions matter: plenty of popular people follow a few others back.

After counting, check each person. There cannot be two influencers, because each would have to follow the other.

Followed by everyone else and following nobody: both, not just one.

Nobody matches: answer minus one.

Quick check

n = 3, follows = [[0, 2], [1, 2], [2, 0]]. Who is the influencer?

ANobody (-1)
BPerson 2
CPerson 0

Show the answer

Nobody (-1). 2 has both others as followers, but 2 follows 0, so it fails the "follows nobody" rule.

Your problem

Everyone follows them

A group chat has n people numbered 0 to n - 1. follows lists one-way follows: [a, b] means a follows b. An influencer is followed by every other person and follows nobody. Return the influencer's number, or -1 if there isn't one.

Example

n = 3, follows = [[0, 2], [1, 2]] → 2

1 ≤ n ≤ 100,000 · 0 ≤ follows.length ≤ 100,000 · 0 ≤ a, b < n · a ≠ b · no follow appears twice

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.

Start coding