Coding-Practice/codingpractice/src/main/java/com/rbhatt/graph/FindTheTownJudge.java at master · rbhatt22/Coding-Practice · GitHub

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package com.rbhatt.graph;

import java.util.*;

//Array
//Graph (updated solution)
//Leetcode question # 997
public class FindTheTownJudge {

    //with graph
    public int findJudge(int N, int[][] trust) {

        int result = -1;

        Map<Integer, List<Integer>> adjacencyList = new HashMap<>();

        for (int i = 0; i < trust.length; i++) {
            List<Integer> list;

            if (adjacencyList.containsKey(trust[i][0])) {
                list = adjacencyList.get(trust[i][0]);
            } else {
                list = new ArrayList<>();
            }

            list.add(trust[i][1]);
            adjacencyList.put(trust[i][0], list);
        }

        for (int i = 1; i <= N; i++) {

            if (!adjacencyList.containsKey(i)) {
                if (result == -1) {
                    result = i;
                } else {
                    result = -1;
                }
            }

        }

        if (result != -1) {
            for (Map.Entry<Integer, List<Integer>> entry : adjacencyList.entrySet()) {
                if (!entry.getValue().contains(result)) {
                    result = -1;
                    break;
                }
            }
        }

        return result;
    }

    /*public int findJudge(int N, int[][] trust) {

        int result = -1;
        Set<Integer> cantBeJudge = new HashSet<>();
        Map<Integer, Set<Integer>> map = new HashMap<>();

        if (trust.length == 0) {
            return 1; // judge is the only one in town.
        }

        for (int i = 0; i < trust.length; i++) {

            Set<Integer> set;

            if (!map.containsKey(trust[i][1])) {
                set = new HashSet<>();
                set.add(trust[i][0]);
                cantBeJudge.add(trust[i][0]);
                map.put(trust[i][1], set);
            } else {
                set = map.get(trust[i][1]);
                set.add(trust[i][0]);
                cantBeJudge.add(trust[i][0]);
                map.put(trust[i][1], set);
            }
        }

        for (Map.Entry<Integer, Set<Integer>> entry: map.entrySet()) {

            if (!cantBeJudge.contains(entry.getKey()) && entry.getValue().size() == N-1) {
                result = entry.getKey();
            }

        }

        return result;
    }*/

    public static void main(String[] args) {

        FindTheTownJudge ob = new FindTheTownJudge();

        System.out.println(ob.findJudge(2, new int[][] {{1,2}} ));

        System.out.println(ob.findJudge(3, new int[][] {{1,3}, {2,3}} ));

        System.out.println(ob.findJudge(3, new int[][] {{1,3}, {2,3}, {3,1}} ));

        System.out.println(ob.findJudge(3, new int[][] {{1,2}, {2,3}}));

        System.out.println(ob.findJudge(4, new int[][] {{1,3}, {1,4}, {2,3}, {2,4}, {4,3}} ));

        System.out.println(ob.findJudge(1, new int[][] {} ));

    }

}