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

• ...

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

...

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