Module Week 10

Find the Town Judge

LeetCode 997

Easy ▼

Source

LeetCode 997 - Find the Town Judge

Problem

In a town, there are n people labelled from 1 to n. There is a rumour that one of these people is secretly the town judge. If the town judge exists, then:

The town judge trusts nobody.
Everybody (except 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] = [a_i, b_i] representing that the person labelled a_i trusts the person labelled b_i. 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.

Function Signature

findJudge(n: int, trust: List[List[int]]) -> int

Examples

Input: n = 2, trust = [[1,2]]
Output: 2

Input: n = 3, trust = [[1,3],[2,3]]
Output: 3

Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

This is a directed graph problem. Each trust relationship [a, b] is a directed edge from a to b. The town judge is the person who has zero outgoing edges and exactly n - 1 incoming edges.

You do not need to build a full graph for this one. Instead, keep a count for each person. For every trust edge [a, b], decrement the count for a (they trust someone, so they cannot be the judge) and increment the count for b (they are trusted by someone). The judge is the person whose count equals n - 1.

⚙ Knowledge Hub: Using Graphs

Create an array count of size n + 1 initialised to zero (1-indexed)
For each [a, b] in trust: do count[a] -= 1 and count[b] += 1
The judge is the person i where count[i] == n - 1
If no such person exists, return -1

Why does this work? The judge trusts nobody (no outgoing edges, so never decremented) and is trusted by all n - 1 others (incremented n - 1 times). Anyone who trusts someone gets decremented at least once, so their count can never reach n - 1.

def findJudge(n, trust):
    count = [0] * (n + 1)
    for a, b in trust:
        count[a] -= 1  # a trusts someone, can't be judge
        count[b] += 1  # b is trusted by someone
    for i in range(1, n + 1):
        if count[i] == n - 1:
            return i
    return -1

int findJudge(int n, vector<vector<int>>& trust) {
    vector<int> count(n + 1, 0);
    for (auto& t : trust) {
        count[t[0]]--;  // trusts someone
        count[t[1]]++;  // is trusted
    }
    for (int i = 1; i <= n; i++)
        if (count[i] == n - 1) return i;
    return -1;
}

public int FindJudge(int n, int[][] trust) {
    int[] count = new int[n + 1];
    foreach (var t in trust) {
        count[t[0]]--;
        count[t[1]]++;
    }
    for (int i = 1; i <= n; i++)
        if (count[i] == n - 1) return i;
    return -1;
}

public int findJudge(int n, int[][] trust) {
    int[] count = new int[n + 1];
    for (int[] t : trust) {
        count[t[0]]--;
        count[t[1]]++;
    }
    for (int i = 1; i <= n; i++)
        if (count[i] == n - 1) return i;
    return -1;
}

Find if Path Exists in Graph

LeetCode 1971

Easy ▼

Source

LeetCode 1971 - Find if Path Exists in Graph

Problem

There is a bi-directional graph with n vertices, where each vertex is labelled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [u_i, v_i] denotes a bi-directional edge between vertex u_i and vertex v_i. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

Function Signature

validPath(n: int, edges: List[List[int]], source: int, destination: int) -> bool

Examples

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2: 0 -> 2 and 0 -> 1 -> 2.

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

This is a standard graph reachability problem. You have solved similar problems before in earlier weeks. Think about which graph traversal technique you would reach for to check whether two nodes are connected.

Either BFS or DFS works perfectly here. Build an adjacency list from the edge list, then start a traversal from source. If you reach destination at any point, return true. If the traversal finishes without visiting it, return false.

⚙ Knowledge Hub: Using Graphs

Build an adjacency list: for each edge [u, v], add v to adj[u] and u to adj[v]
Create a visited set, initialise a queue (BFS) or stack (DFS) with source
While the queue is not empty, pop a node. If it equals destination, return true. Otherwise mark it visited and enqueue all unvisited neighbours
If the loop ends without finding destination, return false

You could also solve this with Union-Find. Group all connected vertices together. Then just check whether source and destination belong to the same group. BFS/DFS is more straightforward here though.

from collections import deque, defaultdict

def validPath(n, edges, source, destination):
    if source == destination:
        return True

    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = set()
    queue = deque([source])
    visited.add(source)

    while queue:
        node = queue.popleft()
        for nb in adj[node]:
            if nb == destination:
                return True
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)

    return False

bool validPath(int n, vector<vector<int>>& edges,
                 int source, int destination) {
    if (source == destination) return true;

    vector<vector<int>> adj(n);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }

    vector<bool> visited(n, false);
    queue<int> q;
    q.push(source);
    visited[source] = true;

    while (!q.empty()) {
        int node = q.front(); q.pop();
        for (int nb : adj[node]) {
            if (nb == destination) return true;
            if (!visited[nb]) {
                visited[nb] = true;
                q.push(nb);
            }
        }
    }
    return false;
}

public bool ValidPath(int n, int[][] edges,
                       int source, int destination) {
    if (source == destination) return true;

    var adj = new List<int>[n];
    for (int i = 0; i < n; i++) adj[i] = new List<int>();
    foreach (var e in edges) {
        adj[e[0]].Add(e[1]);
        adj[e[1]].Add(e[0]);
    }

    var visited = new bool[n];
    var queue = new Queue<int>();
    queue.Enqueue(source);
    visited[source] = true;

    while (queue.Count > 0) {
        int node = queue.Dequeue();
        foreach (int nb in adj[node]) {
            if (nb == destination) return true;
            if (!visited[nb]) {
                visited[nb] = true;
                queue.Enqueue(nb);
            }
        }
    }
    return false;
}

public boolean validPath(int n, int[][] edges,
                          int source, int destination) {
    if (source == destination) return true;

    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }

    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(source);
    visited[source] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int nb : adj.get(node)) {
            if (nb == destination) return true;
            if (!visited[nb]) {
                visited[nb] = true;
                queue.offer(nb);
            }
        }
    }
    return false;
}

Dijkstra: Shortest Reach 2

HackerRank

Hard ▼

Source

HackerRank - Dijkstra: Shortest Reach 2

Problem

Given an undirected graph and a starting node, determine the lengths of the shortest paths from the starting node to all other nodes in the graph. If a node is unreachable, its distance is -1. Nodes are numbered consecutively from 1 to n, and edges have varying weights.

Function Signature

shortestReach(n: int, edges: List[List[int]], s: int) -> List[int]

Parameters

n: the number of nodes in the graph
edges: a 2D array where each element [u, v, w] describes an undirected edge between nodes u and v with weight w
s: the starting node

Return

An array of distances from s to each other node in ascending order of node label, excluding s itself. Use -1 for unreachable nodes.

Examples

Input: n = 4, edges = [[1,2,24],[1,4,20],[3,1,3],[4,3,12]], s = 1
Output: [24, 3, 15]
Explanation: Shortest distances from node 1: to node 2 = 24, to node 3 = 3, to node 4 = 15 (via node 3).

Input: n = 5, edges = [[1,2,5],[2,3,6],[3,4,2],[1,3,15]], s = 1
Output: [5, 11, 13, -1]
Explanation: Node 5 is unreachable, so its distance is -1.

This is the only hard problem in this week. It is a straightforward application of Dijkstra's algorithm, but two things to watch out for: the vertex numbers are 1-based rather than 0-based, and the function must return the distance to every node excluding the start node. Unreachable nodes should have a distance of -1.

Dijkstra's algorithm finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edge weights. Use a priority queue (min-heap) to always process the closest unvisited node next.

There can be multiple edges between the same pair of nodes with different weights. Keep all of them; Dijkstra will naturally pick the shortest route.

Build an adjacency list from the edges (remember: undirected, so add both directions)
Initialise a dist array of size n + 1 with infinity for every node, except dist[s] = 0
Push (0, s) onto a min-heap
While the heap is not empty, pop (d, u). If d > dist[u], skip it (stale entry). Otherwise, for each neighbour (v, w) of u, if dist[u] + w < dist[v], update dist[v] and push (dist[v], v)
Build the result by collecting dist[i] for all i from 1 to n, skipping s. Replace any remaining infinity values with -1

Watch out for duplicate edges between the same pair of nodes. You do not need to filter them out; just add them all to the adjacency list. Dijkstra handles this correctly because it only relaxes an edge if it actually improves the distance.

import heapq
from collections import defaultdict

def shortestReach(n, edges, s):
    adj = defaultdict(list)
    for u, v, w in edges:
        adj[u].append((v, w))
        adj[v].append((u, w))

    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[s] = 0
    heap = [(0, s)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # stale entry, skip it
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    # collect results, skip start node, -1 for unreachable
    result = []
    for i in range(1, n + 1):
        if i == s:
            continue
        result.append(dist[i] if dist[i] != INF else -1)
    return result

vector<int> shortestReach(int n, vector<vector<int>> edges, int s) {
    vector<vector<pair<int,int>>> adj(n + 1);
    for (auto& e : edges) {
        adj[e[0]].push_back({e[1], e[2]});
        adj[e[1]].push_back({e[0], e[2]});
    }

    const int INF = 1e9;
    vector<int> dist(n + 1, INF);
    dist[s] = 0;

    // min-heap: (distance, node)
    priority_queue<pair<int,int>,
        vector<pair<int,int>>,
        greater<pair<int,int>>> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    vector<int> result;
    for (int i = 1; i <= n; i++)
        if (i != s) result.push_back(dist[i] == INF ? -1 : dist[i]);
    return result;
}

static int[] ShortestReach(int n, int[][] edges, int s) {
    var adj = new List<(int v, int w)>[n + 1];
    for (int i = 0; i <= n; i++) adj[i] = new();
    foreach (var e in edges) {
        adj[e[0]].Add((e[1], e[2]));
        adj[e[1]].Add((e[0], e[2]));
    }

    int[] dist = new int[n + 1];
    Array.Fill(dist, int.MaxValue);
    dist[s] = 0;

    // min-heap: (distance, node)
    var pq = new PriorityQueue<int, int>();
    pq.Enqueue(s, 0);

    while (pq.Count > 0) {
        int u = pq.Dequeue();
        foreach (var (v, w) in adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.Enqueue(v, dist[v]);
            }
        }
    }

    var result = new List<int>();
    for (int i = 1; i <= n; i++)
        if (i != s) result.Add(dist[i] == int.MaxValue ? -1 : dist[i]);
    return result.ToArray();
}

static int[] shortestReach(int n, int[][] edges, int s) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(new int[]{e[1], e[2]});
        adj.get(e[1]).add(new int[]{e[0], e[2]});
    }

    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[s] = 0;

    // min-heap: [distance, node]
    PriorityQueue<int[]> pq =
        new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, s});

    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int d = top[0], u = top[1];
        if (d > dist[u]) continue;
        for (int[] edge : adj.get(u)) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }

    List<Integer> result = new ArrayList<>();
    for (int i = 1; i <= n; i++)
        if (i != s) result.add(
            dist[i] == Integer.MAX_VALUE ? -1 : dist[i]);
    return result.stream().mapToInt(Integer::intValue).toArray();
}

MODULE WEEK 10