Problem of the day: Leetcode 997. Find the Town Judge

on

 997. Find the Town Judge

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] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.

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

 

Example 1:

Input: n = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

 

Constraints:

  • 1 <= n <= 1000
  • 0 <= trust.length <= 104
  • trust[i].length == 2
  • All the pairs of trust are unique.
  • ai != bi
  • 1 <= ai, bi <= n



My Solution:
class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> truster(n+1,0);
        vector<int> trusted(n+1,0);
        for(auto &t: trust) {
            truster[t[0]]++;
            trusted[t[1]]++;
        }
        for(int i=1; i<=n; i++) {
            if(truster[i]==0 && trusted[i]==n-1)
                return i;
        }
        return -1;
    }
};

This solution creates two vectors, "truster" and "trusted" of size n+1, and initializes all elements to 0. The "truster" vector keeps track of the number of people each person trusts, while the "trusted" vector keeps track of the number of people that trust each person.

The solution then iterates through the trust vector, which represents the relationships between the people in the town, represented as pairs of integers, where the first integer represents the person who trusts, and the second integer represents the person who is trusted. For each pair, the solution increments the corresponding element of the "truster" vector at the index of the first integer, and increments the corresponding element of the "trusted" vector at the index of the second integer.

After the iteration, the solution then checks for the person who trusts no one (truster[i] == 0) and is trusted by everyone except himself (trusted[i] == n-1). If such a person is found, their label is returned as the result. If no such person is found, the function returns -1.

The time complexity of this solution is O(n) where n is the length of the trust array. This is because the solution iterates through the trust array once and performs a constant number of operations for each pair.

The space complexity of this solution is O(n) where n is the number of people in the town. This is because the solution creates two vectors, each with n+1 elements.

This solution is an optimized approach as it uses a linear time and space complexity which is better than a naive approach which would be O(n^2) as it would check for each person if he trusts nobody and is trusted by everyone except himself.



Comments

Post a Comment