data structures and algorithms
LeetCode: Graphs I In Degree Out Degree

4 min read
#data structures and algorithmsIn Degree Out Degree Intro
LeetCode problems with graph based solutions, specifically dealing with the nodes in and out degrees
What is a In Out Degree?
Has to do with the celebrity vs person graph problem. A celebrity may have many in degrees, but few out degrees. While a person may have many out degrees, but few in degrees.
997. Find the Town Judge ::1:: - Medium
Topics: Degree Counting Array, Depth First Search, Breadth First Search, Hash Table, Graph Theory
Intro
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:
- 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 an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi. If a trust relationship does not exist in trust array, then such a trust relationship does not exist. Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.
| Example Input | Output |
|---|---|
| n = 2, trust = [[1,2]] | 2 |
| n = 3, trust = [[1,3],[2,3]] | 3 |
| n = 3, trust = [[1,3],[2,3],[3,1]] | -1 |
Constraints:
1 ≤ n ≤ 1000
0 ≤ trust.length ≤ 10^4
trust[i].length == 2
All the pairs of trust are unique
ai != bi
1 ≤ ai, bi ≤ n
Abstraction
Judge judy!
Space & Time Complexity
| Solution | Time Complexity | Space Complexity | Time Remark | Space Remark |
|---|---|---|---|---|
| Bug | Error |
|---|---|
Brute Force:
| Aspect | Time Complexity | Space Complexity | Time Remarks | Space Remarks |
|---|---|---|---|---|
Find the Bug:
Solution 1: [Degree Counting] Net Trust Score Single Array - Graph/In Degree Out Degree Counting
def findJudge(self, n: int, trust: List[List[int]]) -> int:
# Note:
# We represent trust as a graph where an edge a -> b means a trusts b.
# The town judge is the only node with In Degree of (n-1), meaning
# everyone trusts them, and an Out Degree of 0, meaning they trust nobody.
# We can track this with a single net score per person instead of using
# separate in and out degree counters.
# for (a -> b) in trust:
# +1 to b's score for incoming trust edges
# -1 to a's score for outgoing trust edges
# The judge if they exist will have a score of (n-1)
# Check:
# Single person, no trust relationships possible or needed,
# they will always be the judge
if n == 1 and not trust:
return 1
# Trust array to track net trust score for each person
# sc: O(n)
trustScore = [0] * (n + 1)
# Check every trust relationship and update the trust score accordingly
# +1 for every person who trusts i
# -1 for every person i trusts
# tc: O(m)
for a, b in trust:
trustScore[a] -= 1
trustScore[b] += 1
# Check every final trust score to see if any person has a score of (n-1)
# tc: O(n)
for person in range(1, n + 1):
if trustScore[person] == n - 1:
return person
# overall: tc O(n + m)
# overall: sc O(n)
return -1| Aspect | Time Complexity | Space Complexity | Time Remarks | Space Remarks |
|---|---|---|---|---|