997. Find the Town Judge

Posted on | Edited on | Views:

LeetCode

Approach 1: Two Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findJudge(int N, int[][] trust) {  
    if (trust.length < N - 1) return -1;
    
    int[] indegrees = new int[N + 1];
    int[] outdegrees = new int[N + 1];

    for (int[] relation : trust) {
        outdegrees[relation[0]]++;
        indegrees[relation[1]]++; 
    }

    for (int i = 1; i <= N; i++) {
        if (indegrees[i] == N - 1 && outdegrees[i] == 0) return i;
    }
    return -1;
    }
}

Approach 2: One Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findJudge(int N, int[][] trust) {
    if (trust.length < N - 1) return -1;
  
    int[] trustScores = new int[N + 1];

    for (int[] relation : trust) {
        trustScores[relation[0]]--;
        trustScores[relation[1]]++; 
    }
    
    for (int i = 1; i <= N; i++) {
        if (trustScores[i] == N - 1) return i;
    }
    return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Graph{
    int vertexNum;
    List<Integer>[] graph;
    int[] inDegrees;
    int[] outDegrees;
    
    Graph(int v){
        this.vertexNum=v;
        this.graph=new ArrayList[this.vertexNum+1];
        for(int i=0;i<=this.vertexNum;i++) this.graph[i]=new ArrayList<>();
        this.inDegrees=new int[this.vertexNum+1];
        this.outDegrees=new int[this.vertexNum+1];
    }
    void addEdge(int a,int b){
        graph[a].add(b);
        this.inDegrees[b]++;
        this.outDegrees[a]++;
    }
}
class Solution {
    public int findJudge(int N, int[][] trust) {
        Graph g=new Graph(N);
        for(int[] i:trust){
            g.addEdge(i[0],i[1]);
        }
        for(int i=1;i<=N;i++){
            if(g.inDegrees[i]==N-1&&g.outDegrees[i]==0) return i;
        }
        return -1;
    }
}
/* First attempt, using topological sort, failed, 52 / 92 test cases passed.
class Graph{
    int vertexNum;
    List<Integer>[] graph;
    int[] inDegrees;
    
    Graph(int v){
        this.vertexNum=v;
        this.graph=new ArrayList[this.vertexNum+1];
        for(int i=0;i<=this.vertexNum;i++) this.graph[i]=new ArrayList<>();
        this.inDegrees=new int[this.vertexNum+1];
    }
    void addEdge(int a,int b){
        graph[a].add(b);
        this.inDegrees[b]++;
    }
}
class Solution {
    public int findJudge(int N, int[][] trust) {
        Graph g=new Graph(N);
        for(int[] i:trust){
            g.addEdge(i[0],i[1]);
        }      
        LinkedList<Integer> q=new LinkedList<>();
        for(int i=1;i<=N;i++){
            if(g.inDegrees[i]==0) q.offer(i);
        }
        int cnt=0;
        int node=-1;
        int[] tmp=g.inDegrees.clone();
        while(!q.isEmpty()){
            node=q.poll();
            cnt++;
            if(cnt==N){
                if(tmp[node]==N-1) return node;
                return -1;
            }
            for(int i:g.graph[node]){
                g.inDegrees[i]--;
                if(g.inDegrees[i]==0) q.offer(i);
            }   
        }
        return -1;
    }
}*/
0%