algoadvance

Leetcode 997. Find the Town Judge

Problem Statement

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

1. The town judge trusts nobody.
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [a, b] represents that the person labeled a trusts the person labeled b.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Strategy

1. Representation and Counting:
   • Use two arrays, inDegree and outDegree to count the number of trusts each person receives and gives respectively.
   • Iterate over the trust array and for each trust[i] = [a, b], increment outDegree[a] and inDegree[b].
2. Identifying the Judge:
   • After populating the inDegree and outDegree, check if there’s a person j such that:
     • inDegree[j] == n - 1 (everyone trusts this person, except themselves).
     • outDegree[j] == 0 (this person trusts no one).
3. Edge Cases:
   • If n is 1 and there are no trust relationships, the single person is the town judge.
   • Handle cases where no such person exists by returning -1.

Time Complexity

• Time Complexity: O(n + t), where n is the number of people and t is the length of the trust array.
• Space Complexity: O(n), due to using the in-degree and out-degree arrays.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        if (n == 1) {
            return 1;  // If there's only one person, they are trivially the judge.
        }
        
        vector<int> inDegree(n + 1, 0);
        vector<int> outDegree(n + 1, 0);
        
        // Populate in and out degrees
        for (const auto& t : trust) {
            int a = t[0];
            int b = t[1];
            outDegree[a]++;
            inDegree[b]++;
        }
        
        // Find the judge
        for (int i = 1; i <= n; ++i) {
            if (inDegree[i] == n - 1 && outDegree[i] == 0) {
                return i;  // This person satisfies the conditions of the judge
            }
        }
        
        // No judge found
        return -1;
    }
};

Clarifying Questions

• Q: Can we assume that the number of people n is always at least 1?
  • A: Yes, the problem guarantees that n is at least 1.
• Q: Can there be multiple trust relationships for the same person in the input trust array?
  • A: Yes, a person can trust multiple different people, and this should be handled correctly by the implementation.
• Q: Will the input array trust always be within the bounds mentioned?
  • A: Yes, assume the input format and bounds are valid as per the problem statement.

With these considerations and strategy, the provided solution efficiently identifies the town judge if they exist.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?