public int findCelebrity(int n) {
        if (n <= 0) return -1;

        // pick potential celebrity
        int low = 0, high = n - 1;
        while (low < high) {
            if (knows(low, high)) ++low;
            else --high;
        }

        // verify celebrity
        for (int i = 0; i < n; ++i) {
            if (i != low) {
                if (knows(low, i) || !knows(i, low)) return -1;
            }
        }
        return low;
    }