# Interesting: same O(n) code(commented), one beats 99.82% run times, the other only beats 9.96%

• below is the code that beats 9.96% run times, O(n), run time 140ms. but i think it minimizes the call of "bool knows(a, b)"

public class Solution extends Relation {
public int findCelebrity(int n) {
int cand = 0;  // set 0 as current candidate
int prevOneKnowsCand = -1;
for (int i=1; i<n; ++i) { // if cand knows i, celebrity must not be this cand, set cand to i. otherwise, i must not be the celebrity, skip it.
if (knows(cand, i)) {
prevOneKnowsCand = cand;  // at least we've already known that "cand" knows the future candidate i
cand = i;
}
}  // at this point, cand does not know anyone coming after him
for (int i=0; i<cand; ++i) { if (knows(cand, i)) { return -1; } }  // at this point, cand does not know anyone else
for (int i=0; i<n; ++i) {
if (i!=cand && i!=prevOneKnowsCand) {  // these 2 ppl know candidate for sure
if (!knows(i, cand)) { return -1; } }
}
return cand;
}
}

below is the code that beats 99.82% run times, O(n), run time 12ms.

public class Solution extends Relation {
public int findCelebrity(int n) {
int cand = 0;  // set 0 as current candidate
// int prevOneKnowsCand = -1;
for (int i=1; i<n; ++i) { // if cand knows i, celebrity must not be this cand, set cand to i. otherwise, i must not be the celebrity, skip it.
if (knows(cand, i)) {
// prevOneKnowsCand = cand;  // at least we've already known that "cand" knows the future candidate i
cand = i;
}
}  // at this point, cand does not know anyone coming after him
for (int i=0; i<cand; ++i) { if (knows(cand, i)) { return -1; } }  // at this point, cand does not know anyone else
for (int i=0; i<n; ++i) {
// if (i!=cand && i!=prevOneKnowsCand) {  // these 2 ppl know candidate for sure
if (!knows(i, cand)) { return -1; } // }
}
return cand;
}
}

why using IF-Statement so slow??? i mean, it should be slower, but maybe not this slow...

• Your first solution gave me 15 ms. You probably hit some temporary problem. I've encountered these before—sometimes even got TLE on a solution that after a few seconds was resubmitted successfully.

• thats whats interesting about lc...lol

• @SergeyTachenov fwiw, I just read the input from end to start (as opposed to start to end) and that enabled a huge performance improvement (95.87% vs 24.69%). Guess that counts as just gaming the test cases on the OJ.

public int findCelebrity(int n) {
int cand = n - 1;
for (int i = n-2; i >= 0; i--) {
if (knows(cand, i)) cand = i;
}
for (int i = n-1; i >= 0; i--) {
if (i != cand && (knows(cand, i) || !knows(i, cand))) return -1;
}
return cand;
}

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