Find the Celebrity

At a party of n people, numbered 0 to n - 1, a celebrity is someone who:

is known by everyone else, and
knows no one else.

You're given an n × n boolean[][] matrix where knows[a][b] is true if person a knows person b. Return the celebrity's number as an OptionalInt, or OptionalInt.empty() if there isn't one. There can be at most one celebrity: if two people were both celebrities, each would have to know the other, which contradicts "knows no one".

LeetCode: 277. Find the Celebrity

Example 1

Text

      0  1  2  3
  0 [ 0, 1, 1, 0 ]
  1 [ 1, 0, 1, 1 ]
  2 [ 0, 0, 0, 0 ]
  3 [ 0, 1, 1, 0 ]
Output: 2

graph LR
    0 --> 1
    0 --> 2
    1 --> 0
    1 --> 2
    1 --> 3
    3 --> 1
    3 --> 2
    style 2 stroke-width:3px

An arrow a → b means a knows b. Every other person has an arrow into 2, and 2 has no arrows out.

Example 2

Text

knows: 0 -> 1, 1 -> 2, 2 -> 0
Output: empty   (everyone knows someone)

Brute force: test every person

For each candidate c, check every other person p: p must know c, and c must not know p. OptionalInt is a container that holds either one int or nothing, so the method can report "no celebrity" without returning null.

Java

import java.util.OptionalInt;

public class Main {
    static boolean isCelebrity(boolean[][] knows, int c) {
        for (int p = 0; p < knows.length; p++) {
            if (p != c && !(knows[p][c] && !knows[c][p])) return false;
        }
        return true;
    }

    static OptionalInt findCelebrity(boolean[][] knows) {
        for (int c = 0; c < knows.length; c++) {
            if (isCelebrity(knows, c)) return OptionalInt.of(c);
        }
        return OptionalInt.empty();
    }

    static boolean[][] matrix(int[][] rows) {
        boolean[][] m = new boolean[rows.length][];
        for (int i = 0; i < rows.length; i++) {
            m[i] = new boolean[rows[i].length];
            for (int j = 0; j < rows[i].length; j++) m[i][j] = rows[i][j] == 1;
        }
        return m;
    }

    public static void main(String[] args) {
        boolean[][] party = matrix(new int[][] {{0, 1, 1, 0}, {1, 0, 1, 1}, {0, 0, 0, 0}, {0, 1, 1, 0}});
        boolean[][] noCelebrity = matrix(new int[][] {{0, 1, 0}, {0, 0, 1}, {1, 0, 0}});
        System.out.println(findCelebrity(party) + " " + findCelebrity(noCelebrity));
    }
}

Output

OptionalInt[2] OptionalInt.empty

Time: O(n²) questions ("does a know b?"). Space: O(1).

Optimal: eliminate one person per question

A single question always rules someone out:

If a knows b, then a isn't the celebrity (a celebrity knows no one).
If a doesn't know b, then b isn't the celebrity (everyone knows the celebrity).

Push everyone onto a stack. While there are at least two people, pop two, ask one question, and push back the one who could still be the celebrity. After n - 1 questions, one candidate is left. That candidate is the only possible celebrity, but not necessarily a real one, so verify them with isCelebrity.

Walkthrough with example 1. The stack (an ArrayDeque, the standard Java stack) starts as [0, 1, 2, 3]:

pop a	pop b	knows[a][b]?	eliminated	push back	stack after
3	2	yes	3	2	[0, 1, 2]
2	1	no	1	2	[0, 2]
2	0	no	0	2	[2]

Candidate 2 passes the check, so the answer is 2.

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.OptionalInt;

public class Main {
    static boolean isCelebrity(boolean[][] knows, int c) {
        for (int p = 0; p < knows.length; p++) {
            if (p != c && !(knows[p][c] && !knows[c][p])) return false;
        }
        return true;
    }

    static OptionalInt findCelebrity(boolean[][] knows) {
        if (knows.length == 0) return OptionalInt.empty();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int p = 0; p < knows.length; p++) stack.push(p);
        while (stack.size() > 1) {
            int a = stack.pop();
            int b = stack.pop();
            stack.push(knows[a][b] ? b : a);
        }
        int candidate = stack.pop();
        return isCelebrity(knows, candidate) ? OptionalInt.of(candidate) : OptionalInt.empty();
    }

    static boolean[][] matrix(int[][] rows) {
        boolean[][] m = new boolean[rows.length][];
        for (int i = 0; i < rows.length; i++) {
            m[i] = new boolean[rows[i].length];
            for (int j = 0; j < rows[i].length; j++) m[i][j] = rows[i][j] == 1;
        }
        return m;
    }

    public static void main(String[] args) {
        boolean[][] party = matrix(new int[][] {{0, 1, 1, 0}, {1, 0, 1, 1}, {0, 0, 0, 0}, {0, 1, 1, 0}});
        boolean[][] noCelebrity = matrix(new int[][] {{0, 1, 0}, {0, 0, 1}, {1, 0, 0}});
        System.out.println(findCelebrity(party) + " " + findCelebrity(noCelebrity));
    }
}

Output

OptionalInt[2] OptionalInt.empty

Time: O(n): n - 1 elimination questions, plus 2(n - 1) to verify. Space: O(n) for the stack.

Same idea with O(1) space

The stack isn't really needed: keep one candidate and compare it with each person in turn. If the candidate knows p, the candidate is eliminated and p becomes the new candidate.

Java

import java.util.OptionalInt;

public class Main {
    static boolean isCelebrity(boolean[][] knows, int c) {
        for (int p = 0; p < knows.length; p++) {
            if (p != c && !(knows[p][c] && !knows[c][p])) return false;
        }
        return true;
    }

    static OptionalInt findCelebrity(boolean[][] knows) {
        if (knows.length == 0) return OptionalInt.empty();
        int candidate = 0;
        for (int p = 1; p < knows.length; p++) {
            if (knows[candidate][p]) candidate = p;
        }
        return isCelebrity(knows, candidate) ? OptionalInt.of(candidate) : OptionalInt.empty();
    }

    static boolean[][] matrix(int[][] rows) {
        boolean[][] m = new boolean[rows.length][];
        for (int i = 0; i < rows.length; i++) {
            m[i] = new boolean[rows[i].length];
            for (int j = 0; j < rows[i].length; j++) m[i][j] = rows[i][j] == 1;
        }
        return m;
    }

    public static void main(String[] args) {
        boolean[][] party = matrix(new int[][] {{0, 1, 1, 0}, {1, 0, 1, 1}, {0, 0, 0, 0}, {0, 1, 1, 0}});
        System.out.println(findCelebrity(party));
    }
}

Output

OptionalInt[2]

Time: O(n). Space: O(1).

Edge cases

Empty party: OptionalInt.empty().
One person: they're trivially the celebrity (there's no one else to check).
No celebrity: the elimination still leaves a candidate, and the verification rejects them.