Blogs Hub

by Sumit Chourasia | Oct 14, 2020 | Category :coding | Tags : algorithm data-structure easy graph leetcode

Find the Town Judge - Tree - Easy - LeetCode

Find the Town Judge - Tree - Easy - LeetCode

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

If the town judge exists, then:

The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.
You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.

If the town judge exists and can be identified, return the label of the town judge.  Otherwise, return -1.

 

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
Example 4:

Input: N = 3, trust = [[1,2],[2,3]]
Output: -1
Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3
 

Constraints:

1 <= N <= 1000
0 <= trust.length <= 10^4
trust[i].length == 2
trust[i] are all different
trust[i][0] != trust[i][1]
1 <= trust[i][0], trust[i][1] <= N

public class Solution {
    Dictionary<int,List<int>> graph = new Dictionary<int,List<int>>();
    HashSet<int> visited = new HashSet<int>();
    Dictionary<int,int> inVertex = new Dictionary<int,int>();
    Dictionary<int,int> outVertex = new Dictionary<int,int>();
    private void AddVertex(int v){
        graph.Add(v, new List<int>());    
    }
    
    private void AddEdge(int source, int destination){
        var edges =graph[source];
        edges.Add(destination);
        graph[source]=edges;
        
        if(inVertex.ContainsKey(destination)){
            inVertex[destination]++;
        }
        else{
            inVertex.Add(destination,1);
        }
        
        if(outVertex.ContainsKey(source)){
            outVertex[source]++;
        }
        else{
            outVertex.Add(source,1);
        }
    }
    
    public int FindJudge(int N, int[][] trust) {
        
        if(trust.Count()==0 && N==1){
            return 1;
        }
        
        for(int i=1;i<=N;i++){
            AddVertex(i);
        }
        
        for(int i=0;i<trust.Length;i++){
            AddEdge(trust[i][0],trust[i][1]);
        }                
        
        foreach(var item in inVertex){
            if(item.Value == N-1 && !outVertex.ContainsKey(item.Key)){
                return item.Key;
            }
        }
        
        return -1;
    }
    
}

Time Complexity: O(V*E)

Space Complexity: O(V)

Where V is the number of Vertices and E is the number of Edges

Contributed By: Sumit Chourasia
Construct the Rectangle - Maths - Easy - LeetCode
Contributed By: Sumit Chourasia
3Sum - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Spiral Matrix - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Rotate Array - Array - Medium - LeetCode