Find the Celebrity

Description

null

Solution(javascript)

// /**
//  * Definition for knows()
//  *
//  * @param {integer} person a
//  * @param {integer} person b
//  * @return {boolean} whether a knows b
//  * knows = function(a, b) {
//  *     ...
//  * };
//  */

// /** 1: brute force O(n^2)
//  * @param {function} knows()
//  * @return {function}
//  */
// const solution = function (knows) {
//   /**
//    * @param {integer} n Total people
//    * @return {integer} The celebrity
//    */

//   return function (n) {
//     let celebrity = -1
//     for (let i = 0; i < n; i++) {
//       let valid = true
//       for (let j = 0; j < n; j++) {
//         if (j === i) {
//           continue
//         }
//         if (knows(i, j) || !knows(j, i)) {
//           valid = false
//           break
//         }
//       }
//       if (valid) {
//         celebrity = i
//       }
//     }
//     return celebrity
//   }
// }


// /** 2: O(N)
//  * @param {function} knows()
//  * @return {function}
//  */
// const solution = function (knows) {
//   /**
//    * @param {integer} n Total people
//    * @return {integer} The celebrity
//    */

//   return function (n) {
//     let celebrity = 0
//     for (let i = 1; i < n; i++) {
//       if (knows(celebrity, i)) {
//         celebrity = i
//       }
//     }
//     for (let i = 0; i < n; i++) {
//       if (i === celebrity) {
//         continue
//       }
//       if (!knows(i, celebrity) || knows(celebrity, i)) {
//         return -1
//       }
//     }
//     return celebrity
//   }
// }

/** 3: Queue
 * @param {function} knows()
 * @return {function}
 */
const solution = function (knows) {
  /**
   * @param {integer} n Total people
   * @return {integer} The celebrity
   */

  return function (n) {
    const candidates = new Array(n).fill(0).map((x, index) => index)
    while (candidates.length >= 2) {
      const a = candidates.shift()
      const b = candidates.shift()
      if (knows(a, b)) {
        candidates.push(b)
      } else {
        candidates.push(a)
      }
    }
    const celebrity = candidates[0]
    for (let i = 0; i < n; i++) {
      if (i === celebrity) {
        continue
      }
      if (!knows(i, celebrity) || knows(celebrity, i)) {
        return -1
      }
    }
    return celebrity
  }
}