1078EasyArrayHash TableGraph Theory

Finding the Trusted Steward

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A hall holds n people numbered 1 through n. Each entry trusts[i] = [a, b] says person a trusts person b, and no entry is listed twice.

The steward is the one person who trusts nobody at all and whom every other person trusts.

Return the steward's number, or -1 when there is none.

Examples

Example 1

Input: n = 1, trusts = []
Output: 1

With one person in the hall, that person trusts nobody and there is nobody left who has to trust them, so they are the steward.

Example 2

Input: n = 4, trusts = [[1, 3], [2, 3], [4, 3]]
Output: 3

Person 3 trusts nobody, and the other three all trust them, which is exactly what the steward has to be.

Example 3

Input: n = 2, trusts = [[1, 2], [2, 1]]
Output: -1

Each person trusts the other, so neither trusts nobody and there is no steward.

Constraints

1 <= n <= 1000
0 <= trusts.length <= 10^4
trusts[i].length == 2
1 <= trusts[i][j] <= n
The two people in an entry are different.
No entry is listed twice.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def find_judge(n: int, trusts: list[list[int]]) -> int:

Java

public int findJudge(int n, int[][] trusts)

The intended approach

Time O(n + m) for n people and m entries.Space O(n) for the two tallies.

Only two tallies per person matter: how many people they trust and how many trust them. The steward is the person trusting nobody who is trusted by everyone else, so their outward tally is nothing and their inward tally is one less than the number of people. So walk the entries once, adding one to the first person's outward tally and one to the second person's inward tally, then sweep the people looking for the one matching both conditions. There can only be one such person, since two of them would each have to trust the other, which their outward tallies forbid. So the first match found is the answer, and no match at all means `-1`.

Pythonentry point: find_judge

def find_judge(n, trusts):
    outward = [0] * (n + 1)
    inward = [0] * (n + 1)
    for pair in trusts:
        outward[pair[0]] += 1
        inward[pair[1]] += 1
    for who in range(1, n + 1):
        if outward[who] == 0 and inward[who] == n - 1:
            return who
    return -1

The obvious version

Test each person outright: scan the whole list of entries to see whether they ever trust anybody, and scan it again for each other person to see whether that person trusts them. Report the first person passing both. Costs the people times the entries rather than two tallies.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_find_judge(n, trusts):
    for who in range(1, n + 1):
        trusts_someone = False
        for pair in trusts:
            if pair[0] == who:
                trusts_someone = True
                break
        if trusts_someone:
            continue
        ok = True
        for other in range(1, n + 1):
            if other == who:
                continue
            found = False
            for pair in trusts:
                if pair[0] == other and pair[1] == who:
                    found = True
                    break
            if not found:
                ok = False
                break
        if ok:
            return who
    return -1

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in