Find the Town Judge

The problem gives us all the directed connections and asks us to find the unique node that everyone else connects to, and this node points to no one.

I first tried to use union-find. This was wrong. Union-find connections are transitive. They work better for undirected connections. This problem has directed connections that don’t transfer. If A trusts B and B trusts C, we can’t say A trusts C.

First Solution: Build Graph Brute Force

Key is the target element, value is the set of elements that trust the key.

// time: O(N²)
// space: O(N²)
int findJudge(int N, vector<vector<int>>& trust) {
    if (N==1) return 1;
    unordered_map<int, unordered_set<int> > g;
    for(auto p : trust) {
        if (g.find(p[1])==g.end())
            g.insert({ p[1], unordered_set<int>{ p[0] } });
        else
            g[p[1]].insert(p[0]);
    }

    for(auto&kv : g) {
        if (kv.second.size() == N-1) {
            bool found=true;
            for(auto&kv2 : g) {
                if (kv2.second.find(kv.first)!=kv2.second.end()) {
                    found=false;
                    break;
                }
            }
            if (found) return kv.first;
        }
    }
    return -1;
}

This approach is not ideal. We only care about connection counts, not paths.

Second Solution: Direct Connection Counting

Track how many people each person trusts and how many people trust each person. Each element needs two counters. So N elements need two vectors.

// time: O(sizeof(trust))
// space: O(2N)
int findJudge(int N, vector<vector<int>>& trust) {
    vector<int> trusts(N+1, 0);
    vector<int> trusted(N+1, 0);
    for(auto& p : trust) ++trusted[p[1]], ++trusts[p[0]];
    for(int i=1;i<=N;++i)
		if (trusted[i]==N-1 && trusts[i]==0) return i;
    return -1;
}

A better solution uses one vector to track trusted - trusts. When it equals N-1, we have our answer.

// time: O(sizeof(trust))
// space: O(N)
int findJudge(int N, vector<vector<int>>& trust) {
    vector<int> balance(N+1, 0);
    for(auto& p : trust) --balance[p[0]], ++balance[p[1]];
    for(int i=1;i<=N;++i) if (balance[i]==N-1) return i;
    return -1;
}

Third Solution: Adjacency Matrix

int findJudge(int N, vector<vector<int>>& trust) {
  vector<vector<int>> knows(N + 1, vector<int>(N + 1));
  for (auto &t : trust) knows[t[0]][t[1]] = 1;
  return findCelebrity(N, knows);
}

int findCelebrity(int n, vector<vector<int>>& knows, int i = 1) {
  // Find the node connected to by all others (might be in cycle)
  for (int j = i + 1; j <= n; ++j) if (knows[i][j]) i = j;
  // Verify: relation is not cyclic
  for (int j = 1; j < i; ++j) if (knows[i][j]) return -1;
  // Verify: this node doesn't connect to all others
  for (int j = 1; j <= n; ++j) if (i != j && !knows[j][i]) return -1;
  return i;
}

With the adjacency matrix preprocessing, space complexity drops to O(1).

Takeaways

Adjacency matrix applications
Connection counting methods

#directed-graph

Find the Kth Largest Element in an Array Find Words That Follow a Bigram Pattern