Java Solution. Easy to understand. Minimized the number of calls to knows. Kindly suggest corrections, if any.


  • 0

    ...

    private static int findCelebrity(int[] candidates) {
    int candidate = -1;

    	if (candidates == null || candidates.length < 1) {
    		return candidate;
    	}
    
    	// find the candidate in the first step. Similar to a kind of voting
    	// algorithm
    	candidate = candidates[0];
    	int prevCandidate = candidates[0];
    
    	// First Pass. Minimize the call to knows method.
    	for (int i = 1; i < candidates.length; i++) {
    		if (knows(candidate, i)) {
    			prevCandidate = candidate;
    			candidate = i;
    		}
    	}
    
    	// Verify whether the candidate is a celebrity or not in two for loops
    	// by minimizing the numbers of calls to knows
    
    	// In the first for loop check whether celebrity doesn't know anyone
    	// before him and and everyone before him knows celebrity except
    	// prevCandidate which has already been checked before
    	for (int i = 0; i < candidate; i++) {
    		if (i != prevCandidate) {
    			if (knows(candidate, i) || !knows(i, candidate)) {
    				return -1;
    			}
    		} else {
    			if (knows(candidate, i)) {
    				return -1;
    			}
    		}
    	}
    
    	// In the second for loop check if everyone after candidate knows him or
    	// not. Vice versa has already been checked in first for loop while
    	// selecting candidate. So we dont need to check if celebrity knows
    	// anyone after him
    	for (int i = candidate + 1; i < candidates.length; 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.