Jc-alt logo
jc
data structures and algorithms

LeetCode: Graphs I In Degree Out Degree

LeetCode: Graphs I In Degree Out Degree
4 min read
#data structures and algorithms

In 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:

  1. The town judge trusts nobody.
  2. Everybody (except for the town judge) trusts the town judge.
  3. 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 InputOutput
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

SolutionTime ComplexitySpace ComplexityTime RemarkSpace Remark
BugError

Brute Force:

AspectTime ComplexitySpace ComplexityTime RemarksSpace 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
AspectTime ComplexitySpace ComplexityTime RemarksSpace Remarks