Question:
I have the following doubt. The exercise is leetcode and the degree of difficulty is "easy". In the statement of the problem it says that there are N people and there can be a judge. Each person a (outgoing) trusts another person b (incoming), forming a two-element list of list. The judge trusts no one, so there must be a list of at least N – 1 of two elements. The solution says that the trust list is iterated taking the two elements of the pair subtracting one (person) from a 1 and the other (person) adding 1. Then it compares it to see if the judge exists resulting in that person or not, resulting in -1. Well I don't understand this algorithm; I have seen it in different ways and they all give the same results. From what I see it is a directed graph and that this must be a common algorithm, but I don't understand the logic. I wanted to know if there is someone who will take the trouble to explain it to me. From already thank you very much.
class Solution2(object):
def findJudge(self, N: int, trust: List[List[int]]) -> int:
"""
:type N: int
:type trust: List[List[int]]
:rtype: int
"""
degrees = [0]*N
for i, j in trust:
degrees[i-1] -= 1
degrees[j-1] += 1
for i in range(len(degrees)):
if degrees[i] == N-1:
return i+1
return -1
if __name__ == '__main__':
print("Example:")
Judge = Solution2()
N = 2
trust = [[1, 2]]
print('J2:', Judge.findJudge(N, trust))
N = 3
trust = [[1, 2], [2, 1]]
print('J2:', Judge.findJudge(N, trust))
N = 3
trust = [[1, 2], [2, 3]]
print('J2:', Judge.findJudge(N, trust))
N = 4
trust = [[1, 3], [2, 3], [1, 4], [2, 4], [4, 3]]
print('J2:', Judge.findJudge(N, trust))
N = 5
trust = [[1, 3], [1, 4], [2, 4], [2, 3], [4, 3],
[5, 4], [5, 3], [4, 5]]
print('J2:', Judge.findJudge(N, trust))
I hope someone can explain it to me.
Answer:
Perhaps the most difficult thing is to understand the statement 🙂
Although camouflaged as a story about a judge and the trust of others, deep down it is a problem of graphs. The problem says that there is a town in which there is at most one person (the judge) who meets the following properties:
- Trust no one
- Everyone else trusts him
and it's about finding that person. To do this, we are given a list of tuples as input, such as: [(1,2), (3,2)] . Each tuple is a pair of citizens and expresses that the first element of the tuple trusts the second. In this example, citizen 1 trusts 2, and citizen 3 trusts 2. Therefore, we see that in this case 2 does not trust anyone, but everyone trusts him, so he would be the judge.
Seen as a graph , the citizens would be nodes of the graph, and the existence of an arrow connecting two nodes indicates that the origin node trusts the destination node. The problem input is a representation of those "arrows".
Seen as a graph with N nodes, the problem would then be stated as: find the node to which N-1 arrows arrive and from which no arrow leaves.
The solution you show is quite clever (and not very obvious). What it does is prepare a list of "counters", one counter for each citizen (for each node of the graph). That counter will be the result of adding all the arrows that arrive at that node, minus all the arrows that leave that node. In this way, the judge (if any) will have a final value of N-1 on that counter, because no arrows come out of it, but N-1 enters.
Having seen this, the code is pretty trivial:
- Initialize the list of counters as
[0]*N(that is, N zeros) - It goes through the list of "trust" (the arrows of the graph) and for each one it decrements the origin node of the arrow and increases the destination node (subtracts the arrows that go out and adds the arrows that go in)
- At the end of this loop we will already have in the array of counters what was explained above, that is, the number of incoming arrows minus the number of outgoing arrows of each node.
- It is enough to look for the node whose counter is worth N-1, that will be the judge. If such a node does not exist, there is no judge, -1 is returned to indicate this.
A slightly more compact and faster implementation could be the following:
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
c = [0]*n
for a,b in trust:
c[a-1] -=1
c[b-1] +=1
if n-1 in c:
return c.index(n-1)+1
else:
return -1
Extension
This solution is a bit confusing because it's not what one would intuitively do. If trying to find which citizen (node) has only incoming arrows in the graph and no outgoing ones, one would tend to think of a solution like the following:
- For each node of the graph I prepare a pair of counters. Initially both counters are 0 (that is, I will store for each node a pair [0,0])
- One counter (the first of that pair) will count the arrows leaving the node
- The other (the second of the pair) will count the arrows that enter
- In the end I will look for the node that has 0 arrows going out and N-1 arrows going in. That will be the judge.
In such an approach we can have these counters in a list. The i -th element of the list would represent the citizen with number i+1 (since the citizens seem to be numbered from 1 onwards, but the indices of the lists start at 0). Thus contadores[3] would be the counters of citizen 4. If, for example, there we have [3, 5] it would mean that 3 arrows come out of citizen 4 and 5 enter (it would not be the judge, because arrows come out of him).
The loop that would count the incoming and outgoing arrows would be like this:
contadores = [ [0,0] for i in range(n) ]
for a,b in trust:
contadores[a-1][0] += 1 # Una flecha más que sale de a
contadores[b-1][1] += 1 # Una flecha más que entra en b
Once the counters have been calculated, it would be a question of searching within the contadores for an element that is worth [0, n-1] since that element would be the judge (since 0 arrows come out and n-1 come in).
This solution I think would be more easily understandable.
What the solution you've posted does instead is use a single counter instead of a couple of them, for each citizen. (In my code c[i] is the counter of citizen i+1).
That counter is decremented for every arrow out, and incremented for every arrow in. Thus the final result can be negative (more arrows come out than go in) or zero (the same number come out as they go in) or positive (more arrows go in than go out). But the funny thing is that the judge would be the only one for whom the final value of this counter is N-1. This value can only appear if N-1 arrows enter and 0 come out, which is the condition that the judge and only he fulfills.