C++ 204ms beats 93%


  • 0
    int findCelebrity(int n) {
            int candidate = 0;
            
            for (int i = 1; i < n; i++) {
                // if candidate knows i, only i will be a valid candidate in [0, i]
                if (knows(candidate, i)) {
                    candidate = i;
                }
            }
            
            // check the two way relation between candidate and the people bofore candidate
            for (int i = 0; i < candidate; i++) {
                if (knows(candidate, i) || !knows(i, candidate)) {
                    return -1;
                }
            }
            // since we already know candidate doesn't know anyone after him, only need to check one way relation
            for (int i = candidate + 1; i < n; i++) {
                if (!knows(i, candidate)) {
                    return -1;
                }
            }
            return candidate;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.