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


  • 3
    M

    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...


  • 0

    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.


  • 0
    W

    thats whats interesting about lc...lol


  • 0

    @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;
        }
    

Log in to reply
 

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