Sunday, April 29, 2018

LeetCode 743 - Network Delay Time

https://leetcode.com/problems/network-delay-time/description/
There are N network nodes, labelled 1 to N.
Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.
Note:
1. N will be in the range [1, 100].
2. K will be in the range [1, N].
3. The length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

X.
We use Dijkstra's algorithm to find the shortest path from our source to all targets. This is a textbook algorithm, refer to this link for more details.
Dijkstra's algorithm is based on repeatedly making the candidate move that has the least distance travelled.
In our implementations below, we showcase both $O(N^2)$ (basic) and $O(N \log N)$ (heap) approaches.

• Time Complexity: $O(N^2 + E)$m where $E$ is the length of times in the basic implementation, and $O(E \log E)$ in the heap implementation, as potentially every edge gets added to the heap.
• Space Complexity: $O(N + E)$, the size of the graph ($O(E)$), plus the size of the other objects used ($O(N)$).
public int networkDelayTime(int[][] times, int N, int K) {
Map<Integer, List<int[]>> graph = new HashMap();
for (int[] edge: times) {
if (!graph.containsKey(edge[0]))
graph.put(edge[0], new ArrayList<int[]>());
}
PriorityQueue<int[]> heap = new PriorityQueue<int[]>(
(info1, info2) -> info1[0] - info2[0]);
heap.offer(new int[]{0, K});

Map<Integer, Integer> dist = new HashMap();

while (!heap.isEmpty()) {
int[] info = heap.poll();
int d = info[0], node = info[1];
if (dist.containsKey(node)) continue;
dist.put(node, d);
if (graph.containsKey(node))
for (int[] edge: graph.get(node)) {
int nei = edge[0], d2 = edge[1];
if (!dist.containsKey(nei))
heap.offer(new int[]{d+d2, nei});
}
}

if (dist.size() != N) return -1;
int ans = 0;
for (int cand: dist.values())
ans = Math.max(ans, cand);
return ans;
}

public int networkDelayTime(int[][] times, int n, int k) {
Map<Integer, Map<Integer, Integer>> graph = buildGraph(times);
Map<Integer, Integer> distances = bfs(graph, k);
if (distances.size() < n) {// \\
return -1;
}
return distances.values().stream().max(Comparator.naturalOrder()).get();
}

private Map<Integer, Integer> bfs(Map<Integer, Map<Integer, Integer>> graph, int k) {
PriorityQueue<NodeDistance> pq = new PriorityQueue<>();

Map<Integer, Integer> distances = new HashMap<>();
distances.put(k, 0);// \\

while (!pq.isEmpty()) {
NodeDistance node = pq.poll();
if (distances.containsKey(node.node))
continue;
distances.put(node.node, node.distance);

}

return distances;
}

Map<Integer, Integer> nbs, int preDistance) {
if (nbs != null) {
for (Entry<Integer, Integer> entry : nbs.entrySet()) {
if (!distances.containsKey(entry.getKey())) {
}
}
}
}

private static class NodeDistance implements Comparable<NodeDistance> {
private int node;
private int distance;

public NodeDistance(int node, int distance) {
super();
this.node = node;
this.distance = distance;
}

@Override
public int compareTo(NodeDistance o) {
return Integer.compare(this.distance, o.distance);
}
}

private Map<Integer, Map<Integer, Integer>> buildGraph(int[][] times) {
Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();

for (int i = 0; i < times.length; i++) {
graph.computeIfAbsent(times[i][0], k -> new HashMap<>()).put(times[i][1], times[i][2]);
}
return graph;

}

basic implementation:
Map<Integer, Integer> dist;
public int networkDelayTime(int[][] times, int N, int K) {
Map<Integer, List<int[]>> graph = new HashMap();
for (int[] edge: times) {
if (!graph.containsKey(edge[0]))
graph.put(edge[0], new ArrayList<int[]>());
}
dist = new HashMap();
for (int node = 1; node <= N; ++node)
dist.put(node, Integer.MAX_VALUE);

dist.put(K, 0);
boolean[] seen = new boolean[N+1];

while (true) {
int candNode = -1;
int candDist = Integer.MAX_VALUE;
for (int i = 1; i <= N; ++i) {
if (!seen[i] && dist.get(i) < candDist) {
candDist = dist.get(i);
candNode = i;
}
}

if (candNode < 0) break;
seen[candNode] = true;
if (graph.containsKey(candNode))
for (int[] info: graph.get(candNode))
dist.put(info[0],
Math.min(dist.get(info[0]), dist.get(candNode) + info[1]));
}

int ans = 0;
for (int cand: dist.values()) {
if (cand == Integer.MAX_VALUE) return -1;
ans = Math.max(ans, cand);
}
return ans;
}

X. DFS
https://leetcode.com/problems/network-delay-time/solution/
We'll maintain dist[node], the earliest that we arrived at each node. When visiting a node while elapsedtime has elapsed, if this is the currently-fastest signal at this node, let's broadcast signals from this node.
To speed things up, at each visited node we'll consider signals exiting the node that are faster first, by sorting the edges.
• Time Complexity: $O(N^N + E \log E)$ where $E$ is the length of times. We can only fully visit each node up to $N-1$ times, one per each other node. Plus, we have to explore every edge and sort them. Sorting each small bucket of outgoing edges is bounded by sorting all of them, because of repeated use of the inequality $x \log x + y \log y \leq (x+y) \log (x+y)$.
• Space Complexity: $O(N + E)$, the size of the graph ($O(E)$), plus the size of the implicit call stack in our DFS ($O(N)$).
Map<Integer, Integer> dist;
public int networkDelayTime(int[][] times, int N, int K) {
Map<Integer, List<int[]>> graph = new HashMap();
for (int[] edge: times) {
if (!graph.containsKey(edge[0]))
graph.put(edge[0], new ArrayList<int[]>());
}
for (int node: graph.keySet()) {
Collections.sort(graph.get(node), (a, b) -> a[0] - b[0]);
}
dist = new HashMap();
for (int node = 1; node <= N; ++node)
dist.put(node, Integer.MAX_VALUE);

dfs(graph, K, 0);
int ans = 0;
for (int cand: dist.values()) {
if (cand == Integer.MAX_VALUE) return -1;
ans = Math.max(ans, cand);
}
return ans;
}

public void dfs(Map<Integer, List<int[]>> graph, int node, int elapsed) {
if (elapsed >= dist.get(node)) return;
dist.put(node, elapsed);
if (graph.containsKey(node))
for (int[] info: graph.get(node))
dfs(graph, info[1], elapsed + info[0]);
}