Skip to main content

< Back to Data Structures and Algorithms

LeetCode 997 · Graphs

Find the Town Judge

The one person everyone else trusts and who trusts no one, by scoring each trust: one down for who gives it, one up for who gets it.

Step through it

Examples
Edge cases
trust (as a graph)
132

n = 3

Step 0 of 2

Output

Running… play or step to the end.

The code

/**
 * Finds the Judge in the town of people.
 * The Jugde trusts nobody, and everybody else trusts the judge.
 * @param {number} n // The number of people in the town
 * @param {number[][]} trust // The array of trust relationship pairs (i.e. [ [1,3], [2,3] ]).
                             // The first index in each pair trusts the last index.
                            // In this example, 1 trusts 3, 2 trusts 3, 3 trusts nobody.
* @return {number} // Either the person that is the judge, or -1 if there is no judge.
*/
const findJudge = (n, trust) => {
  // Handle edge cases with inputs.
  // No comparisons, only one person.
  if (!trust.length && n === 1) return 1
  // No comparisons, more/less than one person.
  if (!trust.length && n !== 1) return -1

  // Assigns a trust score for each person.
  const trustScores = {}

  // O(n) loop over each trust pair.
  for (let i = 0; i < trust.length; i++) {  
      // O(n) loop over each trust relationship.
      trust[i].forEach((currentPerson, idx) => {
          // Only iterate until the end of the array -1, as we're comparing against the next person in the list.
          if (idx !== trust[i].length - 1) {
              // The person we compare against.
              const nextPerson = trust[i][idx+1]

              // Assign / Decrement the currentPerson trustScore, as they trust someone else.
              if (!trustScores[currentPerson]) {
                  trustScores[currentPerson] = -1
              } else {
                  trustScores[currentPerson] = trustScores[currentPerson] - 1
              }

              // Assign / Increment the nextPerson trustScore, as they are trusted.
              if (!trustScores[nextPerson]) {
                  trustScores[nextPerson] = 1
              } else {
                  trustScores[nextPerson] = trustScores[nextPerson] + 1
              }
          }
      })
  }
  
  // O(n) loop over each persons' trust score.
  for (const person in trustScores) {
      // The person is trusted by everyone minus themself.
      if (trustScores[person] === n - 1) {
          // Found the Judge.
          return person
      }
  }
  
  // Nobody is the Judge.
  return -1
}

View it on GitHub (opens in a new tab)